题解 P5545 【[JSOI2016]炸弹攻击2】
xtx1092515503
2020-11-03 08:40:54
# [Portal](https://www.luogu.com.cn/problem/P5545)
直接统计显然是不行的（$n^4$），我们必须得固定一个量，求出满足限制的其它三元组的个数。我选择固定发射源，并且将所有敌人与激光塔按照与当前发射源（之后称其为源点）的向量的倾角排序。
我们考虑符合条件的三元组个数。显然，因为激光塔全在 $x$ 轴下方，敌人全在 $x$ 轴上方，故在射线 $(\text{源点},\text{敌人})$ 两侧的所有激光塔对都可以与该敌人构成合法三元组。
但需要注意的是，当激光塔对与该射线无交点时，这个三元组是不合法的；稍加观察即可发现，有交点的充要条件是两激光塔的向量夹角 $<\pi$。（注意到它强调了没有三点共线的情况，这就使得很多边界情况不用处理。想要研究如何处理边界情况的，推荐[这道题](https://www.luogu.com.cn/problem/P3476)，尽管此种方法会在该题中因为常数过大而T掉）。
于是我们考虑再固定一个激光塔 $j$，则所有在其前方 $\pi$ 范围内的其它激光塔都是合法的。我们可以通过 two-pointers 求出其前方最后一个合法激光塔 $k$。
在 two-pointers 的过程中，我们可以记录以当前节点为端点时的答案 $sum$、合法区间中的激光塔数 $st$、合法区间中的敌人数 $se$。
当一个激光塔进入区间时，$st$ 增加，同时 $sum$ 增加 $se$（该激光塔、$j$、$se$ 中每个敌人，均构成一个三元组）。当一个敌人进入区间时，$se$ 增加。当一个激光塔离开区间时，$st$ 减少。当一个敌人离开区间时，$se$ 减少，并且 $sum$ 减少 $st$（理由同上）。
时间复杂度 $O\Big(S(D+T)\log (D+T)\Big)$，瓶颈在于排序。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
int E,T,B;
ll res;
struct Vector{
int x,y;
Vector(int X=0,int Y=0){x=X,y=Y;}
friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
friend Vector operator *(const Vector &u,const int &v){return Vector(u.x*v,u.y*v);}
friend Vector operator /(const Vector &u,const int &v){return Vector(u.x/v,u.y/v);}
friend ll operator &(const Vector &u,const Vector &v){return 1ll*u.x*v.y-1ll*u.y*v.x;}//cross times
friend ll operator |(const Vector &u,const Vector &v){return 1ll*u.x*v.x+1ll*u.y*v.y;}//point times
double operator !()const{return atan2(y,x);}
friend bool operator <(const Vector &u,const Vector &v){return !u<!v;}
void read(){scanf("%d%d",&x,&y);}
void print(){printf("(%d,%d)",x,y);}
}ene[810],tow[810],bea[810];
pair<Vector,bool>p[1610];
int main(){
scanf("%d",&E);
for(int i=1;i<=E;i++)ene[i].read();
scanf("%d",&B);
for(int i=1;i<=B;i++)bea[i].read();
scanf("%d",&T);
for(int i=1;i<=T;i++)tow[i].read();
for(int o=1;o<=B;o++){
int m=0;
for(int i=1;i<=T;i++)p[m++]=make_pair(tow[i]-bea[o],0);
for(int i=1;i<=E;i++)p[m++]=make_pair(ene[i]-bea[o],1);
sort(p,p+m);
int sum=0,se=0,st=0,len=0;
for(int j=0,k=0;j<m;){
while(len<m&&(p[j].first&p[k].first)>=0){
if(p[k].second==1)se++;
else sum+=se,st++;
len++,k=(k+1)%m;
}
if(p[j].second==0)res+=sum;
if(p[j].second==0)st--;
else sum-=st,se--;
j++,len--;
}
}
printf("%lld\n",res);
return 0;
}
```