CodeForces 1496C Diamond Miner 平面几何

Problem Analysis

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

我们以上图为例，假设存在两条连线 ∣ A B ∣ |AB| ∣AB∣和 ∣ C D ∣ |CD| ∣CD∣相交，不妨设交点为 O O O，那么根据三角形三边关系：任意两边之和大于第三边。那么可以得到下列关系式： ∣ A O ∣ + ∣ D O ∣ > ∣ A D ∣     ① ∣ C O ∣ + ∣ B O ∣ > ∣ B C ∣     ② |AO|+|DO|>|AD| \ \ \ ①\\ |CO|+|BO|>|BC| \ \ \ ② ∣AO∣+∣DO∣>∣AD∣   ①∣CO∣+∣BO∣>∣BC∣   ② ① + ② ①+② ①+②可得 ∣ A D ∣ + ∣ B C ∣ < ∣ A O ∣ + ∣ D O ∣ + ∣ C O ∣ + ∣ B O ∣ = ∣ A B ∣ + ∣ C D ∣ |AD|+|BC| t; while (t--){ int n; cin >> n; n *= 2; int cnt1 = 0, cnt2 = 0; for (int i = 1; i > 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