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

· · 题解

P14634 Voronoi Diagram Returns

问题概述

给定平面上 n 个点 P_1, P_2, \dots, P_n 作为 Voronoi 图的生成点。
对于每个查询点 Q，需要判断 Q 属于 Voronoi 图的：

为避免浮点误差，使用欧氏距离的平方：

d^2((x_1,y_1),(x_2,y_2)) = (x_1-x_2)^2 + (y_1-y_2)^2 .

核心思想

根据 Voronoi 图定义：

Q \in \text{Region}(i) \iff d(Q,P_i) \le d(Q,P_j),\quad \forall j.

因此对每个查询点 Q，只需：

  1. 遍历全部 P_i 计算距离平方 d_i
  2. 找到最小距离 d_{\min}
  3. 统计有多少个 P_i 满足 d_i = d_{\min}

结论如下：

\begin{cases} \text{唯一最小} &\rightarrow \texttt{REGION i} \\ \text{两个最小} &\rightarrow \texttt{LINE i j} \\ \text{三个以上最小} &\rightarrow \texttt{POINT} \end{cases}

Voronoi 图覆盖整个平面，因此 NONE 实际不会出现。

复杂度分析

对每个查询执行 O(n) 距离比较：

O(nq) = 2000 \times 250000 = 5\times10^8

使用 C++ 的整数运算 + 关闭同步可在时限内通过。

样例分析

四个生成点：

P_1=(-5,0),\ P_2=(0,5),\ P_3=(3,4),\ P_4=(1,-6)

查询 Q_1=(-2,2)

\begin{aligned} d_1 &= 13 \\ d_2 &= 13 \\ d_3 &= 29 \\ d_4 &= 68 \end{aligned}

最小距离出现两次 → LINE 1 2

查询 Q_2=(0,0)

25,\ 25,\ 25,\ 36

三次最小 → POINT

查询 Q_3=(2,2)

d_3 = 4\ \text{唯一最小} \Rightarrow \texttt{REGION 3}

总结

本题不需要真正构建 Voronoi 图，只需判断“最小距离出现次数”。
暴力即可通过，代码短且稳定。

参考代码（C++）

// Problem: P14634 [2018 KAIST RUN Fall] Voronoi Diagram Returns
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14634
// Memory Limit: 1024 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,q;
    cin>>n>>q;
    vector<long long> px(n+1),py(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>px[i]>>py[i];
    }
    while(q--)
    {
        long long x,y;
        cin>>x>>y;
        long long bestDist = 999999999999;
        int cnt = 0;
        int r1 = -1,r2 = -1;
        for(int i=1;i<=n;i++)
        {
            long long dx = px[i]-x;
            long long dy = py[i]-y;
            long long d = dx*dx + dy*dy;
            if(d<bestDist)
            {
                bestDist = d;
                cnt = 1;
                r1 = i;
                r2 = -1;
            }
            else if(d==bestDist)
            {
                if(cnt==1)
                {
                    cnt = 2;
                    r2 = i;
                }
                else if(cnt>=2)
                {
                    cnt = 3;
                }
            }
        }
        if(cnt==0)
        {
            cout<<"NONE"<<endl;
        }
        else if(cnt==1)
        {
            cout<<"REGION "<<r1<<endl;
        }
        else if(cnt==2)
        {
            if(r1>r2) swap(r1,r2);
            cout<<"LINE "<<r1<<" "<<r2<<endl;
        }
        else
        {
            cout<<"POINT"<<endl;
        }
    }
}

谢谢大家有耐心看完，加油！