Luogu

分析

枚举发射源,然后以它为源点将敌人和激光塔极角排序然后扫一遍。

对于扫到的每个激光塔,显然它会和每个极角相差 $<\pi$ 的激光塔一起贡献所夹的敌人数的答案。

破环为链,然后预处理出前缀和即可 $\mathcal{O}(n)$ 计算每个发射源的贡献。

总时间复杂度 $\mathcal{O}(n^2\log n)$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3200+10;
const double PI=acos(-1);

int n,m,k; ll ans=0;
struct Point { int x,y; } a[N],b[N],c[N];
pair<double,int> sta[N]; int top=0;
ll sa[N],sc[N],ssa[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
    m=read();
    for (re int i=1;i<=m;++i) b[i].x=read(),b[i].y=read();
    k=read();
    for (re int i=1;i<=k;++i) c[i].x=read(),c[i].y=read();
    for (re int i=1;i<=m;++i) {
        top=0;
        for (re int j=1;j<=n;++j) {
            double ang=atan2(a[j].y-b[i].y,a[j].x-b[i].x);
            sta[++top]=make_pair(ang,0);
            sta[++top]=make_pair(ang+2*PI,0);
        }
        for (re int j=1;j<=k;++j) {
            double ang=atan2(c[j].y-b[i].y,c[j].x-b[i].x);
            sta[++top]=make_pair(ang,1);
            sta[++top]=make_pair(ang+2*PI,1);
        }
        sort(sta+1,sta+top+1);
        for (re int j=1;j<=top;++j) {
            sa[j]=sa[j-1],sc[j]=sc[j-1],ssa[j]=ssa[j-1];
            if (sta[j].second) ++sc[j],ssa[j]+=sa[j];
            else ++sa[j];
        }
        for (re int j=1,p=1;j<=n+k;++j) {
            if (!sta[j].second) continue;
            while (p+1<j+top&&sta[p+1].first<sta[j].first+PI) ++p;
            ans+=ssa[p]-ssa[j]-sa[j]*(sc[p]-sc[j]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 02 月 29 日 11 : 31 AM