Fatman

Some of us may be so fortunate to be thin enough to squeeze through the tiniest hole, others are not. Getting from A to B in a crowded supermarket (even without a cart) can be tough and may require sophisticated navigation: there may seem to be enough room on the one side, but then you may run into trouble with that lady further down...

Let's consider this in an abstract fashion: given an aisle of a certain width, with infinitely small obstacles scattered around, just how fat can a person be and still be able to get from the left side to the right side. Assume that seen from above a (fat) person looks like a circle and the person is incompressible (a person with diameter d cannot go between two obstacles having distance less than d).

Input Specification

The first line of input specifies the number of test cases your program has to process. The input for each test case consists of the following lines:

• One line with the integer length L ( ) and integer width W ( ) of the aisle, separated by a single space.
• One line with the number of obstacles N ( ) in the aisle.
• N lines, one for each obstacle, with its integer coordinates X and Y () separated by a single space.

Output Specification

For each test case given in the input, print a line saying 'Maximum size in test case N is M.', where M is rounded to the nearest fractional part of exactly four digits. M is the maximum diameter of a person that can get through the aisle specified for that test case. N is the current test case number, starting at one.

Example Input

1
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1

Example Output

Maximum size in test case 1 is 2.2361.

---

題目描述：

有一條大道 LxW，會有數個點當做障礙物，目標如果當作圓形，問能從左到右通過不碰撞任何障礙物，
的最大半徑為何？

題目解法：

如果考慮二分答案：

打算建一張可以阻擋的連線圖，如果不能通過則表示圖存在一條由上方到下方的連線。

也就是說使用 BFS 判斷可不可以從上方到下方來判斷。

因此對於每次二分答案就要重新建造一張新的圖。


#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[105];
int bfs(int n) {
    queue<int> Q;
    int used[105] = {}, i;
    Q.push(n);
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(i = 0; i < g[tn].size(); i++) {
            if(used[g[tn][i]] == 0) {
                used[g[tn][i]] = 1;
                Q.push(g[tn][i]);
            }
        }
        if(used[n+1])
            return 1;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    int L, W, n, i, j, k;
    int x[105], y[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &L, &W);
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d", &x[i], &y[i]);
        double l, r, mid;// binary seach radius.
        l = 0, r = W/2.0;
        int cnt = 0;
        while(fabs(l-r) > 1e-10 && cnt++ < 30) {
            mid = (l+r)/2;
            // build graph
            for(i = 0; i <= n+1; i++)
                g[i].clear();
            for(i = 0; i < n; i++) {
                if(y[i]-2*mid < 0)
                    g[n].push_back(i);
                if(y[i]+2*mid > W)
                    g[i].push_back(n+1);
                for(j = i+1; j < n; j++) {
                    int dist = (x[i]-x[j])*(x[i]-x[j])+
                        (y[i]-y[j])*(y[i]-y[j]);
                    if(dist < 4*mid*mid) {
                        g[i].push_back(j);
                        g[j].push_back(i);
                    }
                }
            }
            int ret = bfs(n);
            if(ret == 1)//can't
                r = mid;
            else
                l = mid;
        }
        printf("Maximum size in test case %d is %.4lf.\n", ++cases, l*2);
    }
    return 0;
}

---

說實在，真不懂為什麼二分搜尋法能過，下面的方法卻不能過。

其實二分的答案必然是存在於任兩點之間的距離中。

那麼換句話說，我們考慮依序將答案放大的話，最後就會卡住。

因此使用 disjoint set 來維護這個舉動。

建一次表，把所有邊的大小由小至大排序，依序放入，直到上邊連到下邊即表示這個時候卡住了。


#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
    int x, y, v;
    edge(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const edge &a) const {
        return v < a.v;
    }
};
edge D[20000];
int p[105], r[105];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)    return;
    if(r[x] > r[y])
        r[x] += r[y], p[y] = x;
    else
        r[y] += r[x], p[x] = y;
}
//wrong answer
int main() {
    int testcase, cases = 0;
    int L, W, n, m, i, j, k;
    int x[105], y[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &L, &W);
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d", &x[i], &y[i]);
        m = 0;
        for(i = 0; i < n; i++) {
            D[m] = edge(i, n, y[i]*y[i]), m++;
            D[m] = edge(i, n+1, (W-y[i])*(W-y[i])), m++;
            for(j = i+1; j < n; j++) {
                D[m] = edge(i, j, (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                m++;
            }
        }
        sort(D, D+m);
        double ret = 0;
        for(i = 0; i <= n+1; i++)
            p[i] = i, r[i] = 0;
        for(i = 0; i < m; i++) {
            joint(D[i].x, D[i].y);
            if(findp(n) == findp(n+1))
                ret = sqrt(D[i].v), i = m;
        }
        printf("Maximum size in test case %d is %.4lf.\n", ++cases, ret);
    }
    return 0;
}