题解：P14634 [2018 KAIST RUN Fall] Voronoi Diagram Returns

· · 题解

注意到时限 10s。然后发现 nq\le5\times10^8。所以题目说的什么都是假的，你只需要对于每一个询问暴力枚举，计算距离（的平方），对最小值计数就做完了。时间复杂度 O(nq)。

实际上最大点只跑了 762ms。

int x[N],y[N];
int a[N],top;

void main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    while(q--){
        int x1,y1;cin>>x1>>y1;
        int cur=0x3f3f3f3f;
        top=0;
        for(int i=1,t;i<=n;i++){
            if(cur>(t=(x[i]-x1)*(x[i]-x1)+(y[i]-y1)*(y[i]-y1)))
                cur=t,
                a[top=1]=i;
            else if(cur==t)
                a[++top]=i;
        }
        if(top>=3)cout<<"POINT"<<endl;
        else if(top==2)cout<<"LINE "<<min(a[1],a[2])<<' '<<max(a[1],a[2])<<endl;
        else if(top==1)cout<<"REGION "<<a[1]<<endl;
        else cout<<"NONE"<<endl;
    }
}

如果数据范围再大一些，可以参考 P7883 的思路，随机旋转坐标系再按照 xy 排序，然后二分，取最近的几十个点判断。