枚举$S$中每一个点$i$,
以$i$为原点,对激光塔和敌人进行极角排序。
然后会发现,只需要计算两个防御塔夹角$\in(0,\pi]$之间的敌人数量就好了。
用双指针和前缀和即可处理这个问题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline
using namespace std;
const int N=3205,M=1e6+5,Max=2e5;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Vec
{
int x,y,op;
Vec(int x=0,int y=0,int op=0):x(x),y(y),op(op){}
bool sign(){return x?x>0:y>0;}
}a[N],b[N],c[N],e[N<<1];
I ll cross(const Vec &a,const Vec &b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
bool cmp(Vec a,Vec b){return a.sign()==b.sign()?cross(a,b)<0:a.sign()<b.sign();}
int f[N],g[N],s[N],D,S,T,cnt;
int main()
{
qr(D);
for(int i=1;i<=D;i++)qr(a[i].x),qr(a[i].y);
qr(S);
for(int i=1;i<=S;i++)qr(b[i].x),qr(b[i].y);
qr(T);
for(int i=1;i<=T;i++)qr(c[i].x),qr(c[i].y);
ll ans=0;
for(int i=1;i<=S;i++)
{
cnt=0;
for(int j=1;j<=D;j++)e[++cnt]=Vec(a[j].x-b[i].x,a[j].y-b[i].y,0);
for(int j=1;j<=T;j++)e[++cnt]=Vec(c[j].x-b[i].x,c[j].y-b[i].y,1);
sort(e+1,e+cnt+1,cmp);
for(int j=1;j<=cnt;j++)e[j+cnt]=e[j];
for(int j=1;j<=cnt*2;j++)
{
s[j]=s[j-1],f[j]=f[j-1],g[j]=g[j-1];
if(e[j].op)g[j]+=s[j],++f[j];else ++s[j];
}
for(int j=1,k=1;j<=cnt;j++)if(e[j].op)
{
if(k<j)k=j;
while(k+1<j+cnt&&cross(e[j],e[k+1])<0)++k;
ans+=g[k]-g[j]-1ll*s[j]*(f[k]-f[j]);
}
}
qw(ans);puts("");
return 0;
}
最后一次更新于2020-05-23
0 条评论