hdu

最近点对

题目链接
Quoit Design

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 45620 Accepted Submission(s): 11871

Problem Description
Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

Input
The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

Output
For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input
2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output
0.71
0.00
0.75

求最近点对问题, 很容易想到用分治解决,只不过刚开始容易忽略边界问题,导致超时.这道题限时5s,也算是很少见的了.
最近点对问题至少是两个点,所以边界为2个点和3个点的情况,之所以有3个点的情况是因为当n=3时,二分时会把它分成2个点和1个点,所以这是为了避免1个点的情况发生.
点对points[MAX]按照x从小到大,y从小到大的排序方式排好,然后一分为二mid = (left + right) / 2.最近点对无非出现在A = points[left, mid], B = points[mid+1, right],或者{A, B}之间.递归一下仅省第3种情况需要考虑.
A,B种的最小距离分别为minA, minB, 取 minist = min(minA, minB).
若A, B之间存在两点的距离 < minist, 则A, B中的点x坐标到points[mid].x的距离必然小于minist.由此可获得points[lef, rig]序列, 只需要计算此序列任一两点的距离即可.
以下是我没想到的.
这是个双重循环, 为了进一步优化, 可以设想极限情况下, 左边一点在右边最多有几个点与之满足.画图可知最多有6个点.

代码比1年前写的优雅很多.

double类型输入需要使用”%lf”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#define MAX 100002

using namespace std;

typedef struct node
{
    double x, y;
    double dist(const node no)
    {
        return sqrt(pow(x-no.x, 2)+pow(y-no.y, 2));
    }
    bool operator < (const node p) const
    {
        if(x == p.x)return y < p.y;
        else return x < p.x;
    }
} Node;

Node points[MAX];

/**
* 获取最近两点距离
*/
double fun(int left, int right)
{
    if(left+1 == right)  //2个点
    {
        return points[left].dist(points[right]);
    }
    else if(left+2 == right) //3个点
    {
        double d1 = points[left].dist(points[left+1]),
               d2 = points[left].dist(points[right]),
               d3 = points[left+1].dist(points[right]);
        d1 = d1 < d2 ? d1:d2;
        return d1 < d3 ? d1:d3;
    }
    int mid = (left+right) >> 1;
    double dist = min(fun(left, mid), fun(mid+1, right));
    /*
        从中点向两边找距离中点x不大于dist的点
    */
    int lef = mid, rig = mid;
    while(lef-1>=left && points[lef-1].x-points[mid].x < dist)lef--;
    while(rig+1<=right && points[rig+1].x-points[mid].x < dist)rig++;
    for(int i=lef; i<rig; i++)
    {
        for(int j=i+1, k=1; j<=rig; j++, k++)
        {
            if(k>6) //对于左边任一点,右边极限情况下不超过6个
            {
                k=0;
                break;
            }
            dist = min(dist, points[i].dist(points[j]));
        }
    }
    return dist;
}

int main()
{
    int n;
    double ans;
    while(scanf("%d", &n), n!=0)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%lf %lf", &points[i].x, &points[i].y);
        }
        sort(points, points+n);
        ans = fun(0, n-1);
        printf("%.2f\n", ans/2.0);
    }
    return 0;
}