lb2003的个人博客

枚举$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;
}