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;
}