【HDU】3656 Fire station

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define MAXN 5000
  6 #define MAXM 60
  7 #define INF 0x7FFFFFFF
  8 using namespace std;
  9 int n, m, size;
 10 int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
 11 int H[MAXM], S[MAXM], C[MAXN], a[MAXN];
 12 int dis[MAXM][MAXM];
 13 bool vis[MAXM];
 14 struct Point {
 15     int x, y;
 16 };
 17 Point p[MAXM];
 18 int DIS(int i, int j) {
 19     int x, y;
 20     x = p[i].x - p[j].x;
 21     y = p[i].y - p[j].y;
 22     return x * x + y * y;
 23 }
 24 void Init() {
 25     int i;
 26     for (i = 0; i <= n; i++) {
 27         R[i] = i + 1;
 28         L[i + 1] = i;
 29         U[i] = D[i] = i;
 30         S[i] = 0;
 31         H[i] = -1;
 32     }
 33     R[n] = 0;
 34     size = n + 1;
 35 }
 36 void Link(int r, int c) {
 37     U[size] = c;
 38     D[size] = D[c];
 39     U[D[c]] = size;
 40     D[c] = size;
 41     if (H[r] < 0)
 42         H[r] = L[size] = R[size] = size;
 43     else {
 44         L[size] = H[r];
 45         R[size] = R[H[r]];
 46         L[R[H[r]]] = size;
 47         R[H[r]] = size;
 48     }
 49     S[c]++;
 50     C[size++] = c;
 51 }
 52 int A() {
 53     int i, j, k, res;
 54     memset(vis, false, sizeof(vis));
 55     for (res = 0, i = R[0]; i; i = R[i]) {
 56         if (vis[i])
 57             continue;
 58         res++;
 59         for (j = D[i]; j != i; j = D[j]) {
 60             for (k = R[j]; k != j; k = R[k])
 61                 vis[C[k]] = true;
 62         }
 63     }
 64     return res;
 65 }
 66 void Remove(int c) {
 67     int i;
 68     for (i = D[c]; i != c; i = D[i]) {
 69         L[R[i]] = L[i];
 70         R[L[i]] = R[i];
 71     }
 72 }
 73 void Resume(int c) {
 74     int i;
 75     for (i = D[c]; i != c; i = D[i])
 76         L[R[i]] = R[L[i]] = i;
 77 }
 78 bool Dance(int now) {
 79     if (now + A() > m)
 80         return false;
 81     if (R[0] == 0)
 82         return true;
 83     int i, j, temp, c;
 84     for (temp = INF, i = R[0]; i; i = R[i]) {
 85         if (S[i] < temp) {
 86             temp = S[i];
 87             c = i;
 88         }
 89     }
 90     for (i = D[c]; i != c; i = D[i]) {
 91         Remove(i);
 92         for (j = R[i]; j != i; j = R[j])
 93             Remove(j);
 94         if (Dance(now + 1))
 95             return true;
 96         for (j = L[i]; j != i; j = L[j])
 97             Resume(j);
 98         Resume(i);
 99     }
100     return false;
101 }
102 bool OK(int mid) {
103     int i, j;
104     Init();
105     for (i = 1; i <= n; i++) {
106         for (j = 1; j <= n; j++) {
107             if (dis[i][j] <= mid)
108                 Link(i, j);
109         }
110     }
111     return Dance(0);
112 }
113 int main() {
114     int T, i, j, cnt;
115     int high, low, mid;
116     scanf("%d", &T);
117     while (T--) {
118         scanf("%d%d", &n, &m);
119         for (i = 1; i <= n; i++)
120             scanf("%d%d", &p[i].x, &p[i].y);
121         for (cnt = 0, i = 1; i <= n; i++) {
122             for (j = i; j <= n; j++)
123                 a[cnt++] = dis[i][j] = dis[j][i] = DIS(i, j);
124         }
125         sort(a, a + cnt);
126         cnt = unique(a, a + cnt) - a;
127         for (low = 0, high = cnt; low < high;) {
128             mid = (low + high) >> 1;
129             if (OK(a[mid]))
130                 high = mid;
131             else
132                 low = mid + 1;
133         }
134         printf("%lf\n", sqrt((double) a[low]));
135     }
136     return 0;
137 }