传送门
A
枚举 fort 然后对 drone 和 power 极角排序，设 drone \(i\) 极角为 \(a_i\)，power \(i\) 极角为 \(b_i\)。则 power \((i,j)\) 与 drone \(k\) 和当前 fort 组成的点集合法，其充要条件为 \(b_i<a_k<b_j\) 且 \(b_j-b_i<\pi\)。考虑对每个合法的 \((i,j)\) 拆贡献，答案即为 \(\sum_{i=1}^{t}{(cntr_i-cntl_i)\times sum_i}\)。\(cntl_i\) 表示以 \(i\) 为左端点的合法区间数，\(sum_i\) 表示小于 \(b_i\) 的 \(a_k\) 个数。时间复杂度 \(O(n^2 \log n)\)。
#include<bits/stdc++.h>
#define PI acos(-1)
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define ll long long
using namespace std;
const int N=3010;
using vii=vector<int>;
struct node
{int x,y;double ang;bool operator <(const node &x)const{return ang<x.ang;}
}a[N],b[N],c[N];
int n,m,t;
int main()
{freopen("ambitious.in","r",stdin);freopen("ambitious.out","w",stdout);while(cin>>n&&n){ll ans=0;rep(i,1,n)cin>>a[i].x>>a[i].y;cin>>m;rep(i,1,m)cin>>b[i].x>>b[i].y;cin>>t;rep(i,1,t)cin>>c[i].x>>c[i].y;rep(i,1,m){rep(j,1,n)a[j].ang=atan2(a[j].y-b[i].y,a[j].x-b[i].x);sort(a+1,a+n+1);rep(j,1,t)c[j].ang=atan2(c[j].y-b[i].y,c[j].x-b[i].x);sort(c+1,c+t+1);rep(j,1,n)a[j+n].ang=a[j].ang+PI*2;rep(j,1,t)c[j+t].ang=c[j].ang+PI*2;vii ci(t*2+1,0),s(t*2+1,0);int p=1;rep(j,1,t){while(p<=2*t&&c[p].ang<c[j].ang+PI)p++;ci[j]-=(p-j-1);ci[j+1]+=(p-j-1);ci[j+1]++;ci[p]--;}rep(j,1,2*t)ci[j]+=ci[j-1];p=1;rep(j,1,2*t){while(p<=2*n&&a[p].ang<c[j].ang)p++,s[j-1]++;while(p<=2*n&&a[p].ang<c[j+1].ang)p++,s[j]++;}rep(j,1,2*t)s[j]+=s[j-1],ans+=1ll*ci[j]*s[j-1];}cout<<ans<<"\n";}return 0;
}