2020 ICPC Asia Taiwan Online Programming Contest C Circles

这道题真是忽略了过程就会错，以后再也不一有点思路直接写了。
题目链接++++++++++++++++++++++++
&&&&& 题意大体是刚开始给你n个圆心，游戏开始后每个圆的半径开始以相同的速度增长，当一个圆碰到另一个圆时圆停止增长。这样的话，随着圆的增长其他圆的半径也会被限制（这是动态变化的，肯定最小的两个圆先停止增长，然后其他圆心半径变化，每次需找最小值，可以用优先队列），并不是找到距离每个圆心最近的那个圆心就是停止生长的位置，
题目如下
There are n magical circles on a plane. They are centered at (x1, y1),(x2, y2), . . . ,(xn, yn), respectively. In the beginning, the radius of each circle is 0, and the radii of all magical circles will grow at the same rate. When an magical circle touches another, then it stops growing. Write a program to calculate the total area of all magical circles at the end of growing.

输入描述:
The first line contains an integer n to indicate the number of magical circles. The i-th of thefollowing n lines contains two space-separated integers xi and yi indicating that the i-th magicalcircle is centered at (xi , yi).
输出描述:
Output the total area of the circles.

输入
复制
3
0 0
0 1
2 0
输出
复制
8.639379797371932

输入
复制
4
0 0
1 0
1 1
0 1
输出
复制
3.14159265359

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double pi = acos(-1.0);
 
struct Node
{
    
    double dis;
    int a, b;
    bool operator < (const Node &x) const
    {
    
        return dis > x.dis;
    }
};
priority_queue<Node> Q;
 
int v[MAXN];
double px[MAXN], py[MAXN], ans[MAXN];
 
inline double getdis(int a, int b)
{
    
    double X = abs(px[a] - px[b]);
    double Y = abs(py[a] - py[b]);
    return sqrt(X * X + Y * Y);
}
 
int main()
{
    
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &px[i], &py[i]);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            Q.push((Node){
    getdis(i, j) / 2.0, i, j});
    while(!Q.empty())
    {
    
        Node x = Q.top(); Q.pop();
        if(v[x.a] && v[x.b]) continue;
        else if(!v[x.a] && !v[x.b])
        {
    
            v[x.a] = v[x.b] = 1;
            ans[x.a] = ans[x.b] = x.dis;
            for(int i = 1; i <= n; ++i)
            {
    
                if(!v[i]) Q.push((Node){
    getdis(x.a, i) - x.dis, x.a, i});
                if(!v[i]) Q.push((Node){
    getdis(x.b, i) - x.dis, x.b, i});
            }
        }
        else
        {
    
            if(v[x.a]) swap(x.a, x.b);
            if(abs(x.dis + ans[x.b] - getdis(x.a, x.b)) < EPS)
            {
    
                v[x.a] = 1, ans[x.a] = x.dis;
                for(int i = 1; i <= n; ++i)
                    if(!v[i]) Q.push((Node){
    getdis(x.a, i) - x.dis, x.a, i});
            }
        }
    }
    double sum = 0;
    for(int i = 1; i <= n; ++i)
        sum += ans[i] * ans[i] * pi;
    printf("%.15f\n", sum);
    return 0;
}

这道题又给我了一种新的思路，牛逼！！！！！！！！！