Quoit Design(HDOJ 1007)
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
My Code
这题翻译出来很奇怪，不过勉强能理解题意（才怪）
大意就是给你许多玩具的坐标，让你求一个最大的圆环半径，使得圆环最多只能套住一个玩具。
这题用贪心的思维，就是求最近点对距离的一半，就是答案。
最近点对问题是一个经典的分治算法，首先，按照横坐标x排序，然后我们将它对半分成两个区间，可以以最中间的那个点为中心，画条线为中轴。
然后我们分别求出左右区间的最近点对距离，然后取小的那个为d。
然后合并区间后，有两种情况：
第一种，最近点对都在左区间或都在右区间，那么合并后的最近点对距离就是d。
第二种，最近点对分别在左右两个区间，如果直接枚举两边点之间的距离显然是不行的。所以需要剪枝。
首先，如果一个点的距离到中轴的距离（与中间点的横坐标之差）都比d大了，那么它和另一个区间的点的距离显然大于d，可以不用管了。于是我们把区间缩短到了，以中轴为中心，左右各延伸d的一个区间。
如果之间枚举这个区间内的点复杂度还是太高，于是，我们这次按照y从小到大排序，然后逐个枚举。当两个点纵坐标之差大于d了，那么就可以枚举下一个点了，因为之后的点纵坐标之差更大。
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n;
struct node
{
double x, y;
} a[maxn];
node tmp[maxn];
bool cmp1(node x, node y)//按x排序
{
if (x.x == y.x)
return x.y < y.y;
return x.x < y.x;
}
bool cmp2(node x, node y)//按y排序
{
if (x.y == y.y)
return x.x < y.x;
return x.y < y.y;
}
double dis(node x, node y)//计算距离
{
return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
double find(int l, int r)
{
if (l == r) //一个点算不了，返回无穷大
return inf;
if (r - l == 1) //两个点，那最小距离就是两点间的距离
return dis(a[l], a[r]);
int m = (l + r) >> 1;//二分，先在左右区间分别找区间内最近两点的距离
//有两种情况，第一种，最近的两点都在左区间或都在右区间，第二种，一个在左区间，一个在右区间
double d = min(find(l, m), find(m + 1, r)); //第一种情况的话，这就是答案了，下面是讨论第二种情况
int t = 0;
for (int i = l; i <= r; i++)
if (fabs(a[i].x - a[m].x) <= d) //如果到m的横坐标距离都大于d的，两点间的距离就更大于d了
tmp[t++] = a[i];
sort(tmp, tmp + t, cmp2);//将这些可能的点按y排序
for (int i = 0; i < t; i++)
for (int j = i + 1; j < t; j++)
{
if (tmp[j].y - tmp[i].y > d)//同理纵坐标差都超过d了的，后面的显然距离更大了，直接退出
break;
d = min(d, dis(tmp[i], tmp[j]));//挨个比较，看看有没有更近的两个点。
}
return d;
}
int main()
{
while (~scanf("%d", &n) && n)
{
for (int i = 0; i < n; i++)
scanf("%lf%lf", &a[i].x, &a[i].y);
sort(a, a + n, cmp1); //按x排序，分治
printf("%.2lf
", find(0, n - 1) / 2);//答案就是最近点距离的一半
}
return 0;
}
OωO
