HDU1007 Quoit Design

Quoit Design

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

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

0 0

1 1

-1.5 0

0 0

0 1.5

Sample Output

0.71

0.00

0.75

扩充词汇时间：

quoit

英 [kɔɪt] 美 [kwɔɪt, kɔɪt]

n.金属环，铁环，绳圈; vt.掷（圈环）;

pitched

英 [pɪtʃt] 美 [pɪtʃt]

adj.有坡度的; v.投( pitch的过去式和过去分词 )；把…定于特定角度;

configuration

英 [kənˌfɪgəˈreɪʃn] 美 [kənˌfɪgjəˈreɪʃn

n.配置; 布局，构造

最近点对问题，结果输出最近点距离d的一半。N规模达到10万，可以用分治法求解。首先按横坐标从小到大排序，找一个中间点将其分为左右两个部分，则最近点对可能是：①两个点都在左边；②两个点都在右边；③一个点在左边，一个点在右边。先根据①②求出一个可能的D，则D>=d，求第③种情况时不必将每个点都枚举，可以根据D的值剔除明显不可能的点，再计算。

AC代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 struct point
 9 {
10     double x,y;
11 }p[100001];
12 int a[100001]; 
13 bool compare_x(point a,point b)//按横坐标大小排序 
14 {
15     return a.x<b.x;
16 }
17 bool compare_y(int a,int b)//纵坐标 
18 {
19     return p[a].y<p[b].y;
20 }
21 double dis(point a,point b)//两点间距离 
22 {
23     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
24 }
25 double fun(int l,int r)
26 {
27     if(l+1==r) return dis(p[l],p[r]);
28     else if(l==r) return 1<<30;
29     int mid=(l+r)>>1;
30     double d=min(fun(l,mid),fun(mid+1,r));
31     int cnt=0;
32     
33     for(int i=l;i<=r;i++)
34     if(fabs(p[mid].x-p[i].x)<=d)//剔除掉横坐标差大于D的点，这些点距离不可能小于D 
35     a[++cnt]=i;
36     sort(a+1,a+cnt+1,compare_y);
37     
38     for(int i=1;i<=cnt;i++)
39     {
40         for(int j=i+1;j<=cnt;j++)
41         {
42             if(p[a[j]].y-p[a[i]].y>=d) break;
43             d=min(d,dis(p[a[i]],p[a[j]]));
44         }   
45     }
46     
47     return d;
48 }
49 int main()
50 {
51     int n,i;
52     while(scanf("%d",&n),n>0)
53     {
54         for(i=1;i<=n;i++)
55         scanf("%lf%lf",&p[i].x,&p[i].y);
56         sort(p+1,p+n+1,compare_x);
57         double ans=fun(1,n)/2;//最近点对的距离除以2 
58         printf("%.2lf
",ans);
59     }
60     
61 }

View Code

1100多ms水过，以后会优化了再来优化