Quoit Design
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.
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
Author
CHEN, Yue
Source
题目大意:给定平面上的N个点，现在用半径最小的圆覆盖其中的两个点，求最小半径。
显然题目是求最近点对，答案即为 最小距离/2
下面讲用分治算法求最近点对
首先将给定点按x坐标排序
下面定义一个过程 solve(L, R) 求点L到点R间的最近点对
对于当前的 solve(L, R) 我们把点分成[L, mid], [mid + 1, r]两部分
先递归求两点在同一点集的最近点对 设最近点对距离为D
对于两点在不同点集的点对,我们进行处理
显然，只有离分界点距离小于D的点有可能更新答案
用x坐标初步筛出可能更新答案的点
将筛出的点按y坐标排序
显然，对于点P(a, b)
当且仅当点Q(x, y) 满足 |a-x| < d 且 |b-y| < d 时，点对(P, Q) 才可更新答案
对于点集[L, mid]中的任一点，能证明点集[mid + 1, r]中能与它更新答案的点最多只有6个
以下是证明图
所以我们可以用指针更新点集[mid + 1, r]中可更新答案的点的范围
然后暴力更新答案
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 100010;
int N;
struct point{
double x, y;
inline point (double a = 0, double b = 0){
x = a; y = b;
}
}p[MaxN], que1[MaxN], que2[MaxN];
double D;
inline bool cmp_x(const point &a, const point & b){
return a.x < b.x;
}
inline bool cmp_y(const point &a,const point &b){
return a.y < b.y;
}
inline double dist(const point &a,const point &b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline void solve(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
solve(l, mid), solve(mid + 1, r);
int t1 = 0, t2 = 0;
for (int i = l; i <= mid; ++i)
if (p[i].x > p[mid + 1].x - D) que1[++t1] = p[i];
else break;
for (int i = mid + 1; i <= r; ++i)
if (p[i].x < p[mid].x + D) que2[++t2] = p[i];
else break;
sort(que1 + 1, que1 + t1 + 1, cmp_y);
sort(que2 + 1, que2 + t2 + 1, cmp_y);
int t = 1, w = 1;
for (int i = 1; i <= t1; ++i){
while (t < t2 && que2[t].y < que1[i].y - D) ++t;
while (w < t2 && que2[w+1].y < que1[i].y + D) ++w;
for (int j = t; j <= w; ++j)
D = min(D, dist(que1[i], que2[j]));
}
}
int main(){
for (;;){
scanf("%d", &N);
if (!N) break;
D = 1e8;
for (int i = 1; i<= N; ++i)
scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + N + 1, cmp_x);
solve(1,N);
printf("%.2lf\n",D/2);
}
}
评论 (0)
