CodeForces 1496C Diamond Miner 平面几何

Problem Analysis

一道普通的几何题。矿工在轴上，矿在轴上。坐标可能不位于第一象限，但根据象限对称原理，我们将所有的矿工和矿都转移到第一象限，其距离与转移前是等效的。

我们以上图为例，假设存在两条连线和相交，不妨设交点为，那么根据三角形三边关系：任意两边之和大于第三边。那么可以得到下列关系式：

可得

那么考虑最小值的情况：应该是这条连线无交点时，连线长度求和。

#include <bits/stdc++.h>
#define
using namespace std;
const int N = 1e6 + 10;
db xx[N], yy[N];
signed main(){
    ios_base::sync_with_stdio(0);
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        n *= 2;
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= n; i++){
            int x, y; cin >> x >> y;
            if (x == 0) xx[++cnt1] = abs(y);
            else yy[++cnt2] = abs(x);
        }
        sort(xx + 1, xx + 1 + cnt1);
        sort(yy + 1, yy + 1 + cnt2);
        n /= 2;
        db ans1 = 0, ans2 = 0;
        for (int i = 1; i <= n; i++) ans2 += sqrt(xx[i] * xx[i] + yy[i] * yy[i]);
        cout << setprecision(15) << std::fixed << ans2 << endl;
    }
    return 0;
}