【JSOI2016】炸弹攻击2

题目

枚举每一个发射源,对于当前发射源(S_k),将激光塔和敌人按照到(S_k)的向量的极角序排序。

如果存在(D_l)在两个激光塔(T_i,T_j)之间,且(T_i,T_j)的夹角小于(pi),那么((T_i,T_j,S_k,D_l))就是一组合法的四元组。

于是直接排序后双指针,对于每一个激光塔(T_i)求出距离最远的夹角不超过(pi)的激光塔(l_i)在哪里,指针扫的过程中我们维护当前这个区间内的答案、激光塔数量、敌人数量;新增一个激光塔,对于当前区间内的每个敌人,能作为(T_j)的都多了一个,于是答案加上区间内敌人的数量;删除一个敌人,那么对于区间内所有的激光塔,能作为(D_l)的都减少了一个,于是答案减去区间内激光塔的数量。

注意到按极角序排序后首位相接可能构成答案,于是将极角(θ in (0,-pi])的激光塔变成(2pi+θ)接在序列的后面即可。

时间复杂度(O(n^2log n))代码

原文地址:https://www.cnblogs.com/asuldb/p/12975478.html