题解 P5545 【[JSOI2016]炸弹攻击2】
seajupiter · · 题解
算法：计算几何+双指针
首先，看数据范围可知，不能够去枚举每一条线段，两两判断是否相交。但是，本题较为特殊的是，满足所有敌人在x轴上方，所有发射源和激光塔在x轴下方。于是
- 分别对每个发射源进行处理
- 对于当前发射源S，把S到所有Di、Ti的向量按照极角排序
- 答案就是满足T1、T2夹角小于180度的（T1，D，T2）三元组的数量。可用Two Pointers思想求解。核心思想即为：对每一个左端点，找出可行区间的右端点。利用前缀和计算出T1为当前左端点，T2在当前区间内的方案数（从头到区间内每个T间D个数的累积和-从头到左端点D的个数累积和*区间内T的个数）
-
注意头尾可能相接构成方案，故可复制一倍做环状处理
最后，给出我个人的代码供大家参考
#include<bits/stdc++.h>
const double pi=3.1415926535;
using namespace std;
void read(int &x)
{
char c=getchar();x=0;int f=1;
while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();x*=f;
}
void read(long long &x)
{
char c=getchar();x=0;int f=1;
while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();x*=f;
}
const int N=1005;
int D,S,T;
struct point
{
long long x,y;
double angle;
point(){}
point(long long x0,long long y0){x=x0;y=y0;angle=atan2(y,x);};
void init(){read(x);read(y);angle=atan2(y,x);}
point operator-(const point &a)const{return point(x-a.x,y-a.y);}
}d[N],s[N],t[N];
typedef point vec;
long long cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
const int onseg=0,onl=1,onr=-1;
int ccw(vec a,vec b)
{
if(cross(a,b)>(long long)0)return onl;
else if(cross(a,b)<(long long)0)return onr;
else return onseg;
}
bool operator<(vec a,vec b){return a.angle>b.angle;}
long long ans;
struct ray
{
vec vc;
bool type;
}v[N<<2];
bool sign(long long x){return x>=0;}
bool cmp(ray a,ray b){return a.vc<b.vc;}
int sd[N<<2],st[N<<2],sum[N<<2];
void solve(point p)
{
for(int i=1;i<=D;i++)v[i]={d[i]-p,0};
for(int i=1;i<=T;i++)v[D+i]={t[i]-p,1};
sort(v+1,v+1+D+T,cmp);
for(int i=1;i<=D+T;i++)v[i+D+T]=v[i];
for(int i=1;i<=(D+T)*2;i++)
{
st[i]=st[i-1];
sd[i]=sd[i-1];
sum[i]=sum[i-1];
if(v[i].type)
{
st[i]++;
sum[i]+=sd[i];
}
else sd[i]++;
}
for(int i=1,j=1;i<=D+T;i++)if(v[i].type)
{
j=max(j,i);
while(j+1<i+D+T&&ccw(v[i].vc,v[j+1].vc)<=0)j++;
ans+=sum[j]-sum[i]-sd[i]*(st[j]-st[i]);
}
}
int main(){
read(D);
for(int i=1;i<=D;i++)d[i].init();
read(S);
for(int i=1;i<=S;i++)s[i].init();
read(T);
for(int i=1;i<=T;i++)t[i].init();
for(int i=1;i<=S;i++)solve(s[i]);
cout<<ans<<endl;
return 0;
}我写这道题时，因为找不到讲的比较详细的题解而走了许多弯路，花了两天才想出统计答案的办法，希望这篇题解能对读者有帮助。