BZOJ4858 : [Jsoi2016]炸弹攻击 2

枚举每个$S$作为原点，将所有$D$和$T$极角排序。

枚举每个$T$，那么另一个$T$需要和当前的$T$夹角不超过$180$度，贡献为内部$D$的个数。

双指针后用前缀和查询区间的贡献即可。

时间复杂度$O(n^2\log n)$。

#include<cstdio>

#include<algorithm>

const int N=810;

int D,S,T,i,j,k,cnt,s[N*4],f[N*4],g[N*4];long long ans;

struct P{

  int x,y,t;

  P(){}

  P(int _x,int _y,int _t){x=_x,y=_y,t=_t;}

  int sgn()const{return x?x>0:y>0;}

}a[N],b[N],c[N],e[N*4];

inline bool cmp(const P&a,const P&b){

  if(a.sgn()!=b.sgn())return a.sgn()<b.sgn();

  return 1LL*a.x*b.y<1LL*a.y*b.x;

}

int main(){

  scanf("%d",&D);

  for(i=1;i<=D;i++)scanf("%d%d",&a[i].x,&a[i].y);

  scanf("%d",&S);

  for(i=1;i<=S;i++)scanf("%d%d",&b[i].x,&b[i].y);

  scanf("%d",&T);

  for(i=1;i<=T;i++)scanf("%d%d",&c[i].x,&c[i].y);

  for(i=1;i<=S;i++){

    cnt=0;

    for(j=1;j<=D;j++)e[++cnt]=P(a[j].x-b[i].x,a[j].y-b[i].y,0);

    for(j=1;j<=T;j++)e[++cnt]=P(c[j].x-b[i].x,c[j].y-b[i].y,1);

    std::sort(e+1,e+cnt+1,cmp);

    for(j=1;j<=cnt;j++)e[j+cnt]=e[j];

    for(j=1;j<=cnt*2;j++){

      s[j]=s[j-1],f[j]=f[j-1],g[j]=g[j-1];

      if(e[j].t)f[j]++,g[j]+=s[j];else s[j]++;

    }

    for(j=k=1;j<=cnt;j++)if(e[j].t){

      if(k<j)k=j;

      while(k+1<j+cnt&&1LL*e[j].x*e[k+1].y<=1LL*e[j].y*e[k+1].x)k++;

      ans+=g[k]-g[j]-s[j]*(f[k]-f[j]);

    }

  }

  return printf("%lld",ans),0;

}