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

· · 题解

P14634 Voronio 题解

思路

首先可以想到 O(nq) 的朴素做法，可是先别急着优化，注意到时限是 10s，于是就可以通过啦。 ^-^

细节

使用一个优先队列（其实可以不用，无所谓反正不会 TLE，方便）维护距离的平方。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll n, q, x[2005], y[2005], a, b;
pair<ll, ll> p1, p2, p3;
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
    }
    while (q--)
    {
        cin >> a >> b;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > ans;
        for (ll i = 1; i <= n; i++)
        {
            ll dis = (a - x[i]) * (a - x[i]) + (b - y[i]) * (b - y[i]);
            ans.push(make_pair(dis, i));
        }
        p1 = ans.top();
        ans.pop();
        p2 = ans.top();
        ans.pop();
        p3 = ans.top();
        ans.pop();
        if (p1.first == p2.first && p1.first == p3.first) cout << "POINT\n";
        else if (p1.first == p2.first) cout << "LINE " << p1.second << " " << p2.second << endl;
        else cout << "REGION " << p1.second << endl;
    }
    return 0;
}