C. Safe Distance（二分 + 并查集）

給定一個$X\times Y$的矩形，里面有$n,(1\le n\le 1000)$個點，我們要從點$(0,0)$走到$(X,Y)$，我們要使過程中與這$n$個點的最小距離最大，輸出這個最大距離。

考慮二分答案？對于給定的$x$，判斷能否從$(0,0)$走到$(X,Y)$，設置$l=0,r=min(di{s}_S,di{s}_T)$，起點距離其他點的最小值，終點距離其他點的最小值。

可以想象成一個半徑為$x$的圓，存在一條路徑可以使這個圓穿過去，如果存在三個點，有兩對不能使這個圓穿過，則這三個點集構成的集團一定不能使圓穿過。

對于任意兩個不同的集團，我們是可以從其中通過的，所以可以考慮用并查集合并，是否存在一條路徑是可行的。

如果可行，當且僅當（上邊界下邊界沒有聯通）（上邊界右邊界沒有連通）（左邊界下邊界沒有聯通）（左邊界有邊界沒有聯通），

簡單的描述一下，就是從$(0,0)$連向$(X,Y)$的某條路徑沒有被隔斷。

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 10;struct Res {double x, y;void read() {scanf("%lf %lf", &x, &y);} }a[N];int fa[N], n, X, Y; // {n + 1, 上表面} {n + 2, 下表面} {n + 3, 左表面} {n + 4, 右表面}int find(int rt) {return rt == fa[rt] ? rt : fa[rt] = find(fa[rt]); }double Dis(Res a, Res b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }bool judge(double x) {for (int i = 1; i <= n + 4; i++) {fa[i] = i;}for (int i = 1; i <= n; i++) {if (a[i].y + x > Y) {int u = find(i), v = find(n + 1);fa[u] = v;}if (a[i].y < x) {int u = find(i), v = find(n + 2);fa[u] = v;}if (a[i].x < x) {int u = find(i), v = find(n + 3);fa[u] = v;}if (a[i].x + x > X) {int u = find(i), v = find(n + 4);fa[u] = v;}for (int j = 1; j < i; j++) {if (Dis(a[i], a[j]) < 2 * x) {int u = find(i), v = find(j);fa[u] = v;}}}if ((find(n + 1) == find(n + 2)) || (find(n + 1) == find(n + 4)) || (find(n + 3) == find(n + 2)) || (find(n + 3) == find(n + 4))) {return false;}return true; } int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d %d", &X, &Y, &n);for (int i = 1; i <= n; i++) {a[i].read();}double l = 0, r = max(X, Y);for (int i = 1; i <= 100; i++) {double mid = 0.5 * (l + r);if (judge(mid)) {l = mid;}else {r = mid;}}printf("%.10f\n", l);return 0; }

總結

以上是生活随笔為你收集整理的C. Safe Distance（二分 + 并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。