题解：P5545 [JSOI2016] 炸弹攻击2

jokersen · 2026-08-10 21:42:35 · 题解

枚举发射源，以当前枚举的作为原点重新建系，将敌人和激光塔按极角排序。

由于敌人都在 x 轴上方而发射源在 x 轴下方，题目的条件等价于两个激光塔的极角分别大于/小于敌人的极角，且激光塔连成线段在发射源上方。

简单绘图可以发现，在发射源上方等价于激光塔张成的极角 <\pi。

于是可以维护满足左右端点极角差 <\pi 且最大的区间，用双指针维护移动区间的答案。

具体地，用 cnt,p,q 分别表示区间中最前面的敌人的前一个激光塔与其它激光塔的贡献，区间中的敌人数，区间中的激光塔数。

当加入一个敌人时 p\gets p+1，删除时 p\gets p-1。激光塔同理。

计算 cnt 的变化：

• 当在后面加入敌人时，它后面目前没有激光塔，cnt 不变。
• 当在后面加入激光塔时，前面的每一个敌人都能新形成一对，cnt\gets cnt+p。
• 当在前面删除敌人时，它后面的所有激光塔原先都会和它造成贡献，cnt\gets cnt-q。
• 当在前面删除激光塔时，不影响最前面的敌人，因此也不影响最前面的敌人的前一个激光塔，cnt 不变。

注意原先的敌人和激光塔形成的是一个环。处理跨越端点可以将点复制一份加在后面，角度加上 2\pi。

#include<bits/stdc++.h>
#define N 805
using namespace std;
using db=long double;
const db pi=acos(-1);
long long ans;
struct point{
    int x,y;db d;bool op;point(){}
    point(int a,int b,bool f){d=atan2(y=b,x=a),op=f;}
}a[N<<2];int D,S,T,dx[N],dy[N],sx[N],sy[N],tx[N],ty[N];
int main(){
    scanf("%d",&D);for(int i=1;i<=D;i++) scanf("%d%d",dx+i,dy+i);
    scanf("%d",&S);for(int i=1;i<=S;i++) scanf("%d%d",sx+i,sy+i);
    scanf("%d",&T);for(int i=1;i<=T;i++) scanf("%d%d",tx+i,ty+i);
    for(int i=1,n=D+T;i<=S;i++){
        for(int j=1;j<=D;j++) a[j]={dx[j]-sx[i],dy[j]-sy[i],true};
        for(int j=1;j<=T;j++) a[j+D]={tx[j]-sx[i],ty[j]-sy[i],false};
        sort(a+1,a+n+1,[](point x,point y){return x.d<y.d;});
        for(int i=1;i<=n;i++) a[i+n]=a[i],a[i+n].d+=pi*2;
        for(int l=1,r=1,cnt=0,p=0,q=0;l<n;a[l++].op?(cnt-=q,p--):(ans+=cnt,q--))
            for(;a[r].d-a[l].d<pi;a[r++].op?p++:(cnt+=p,q++));
    }printf("%lld",ans);
    return 0;
}