點擊打開鏈接

?

Quoit Design

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 61473????Accepted Submission(s): 16298


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 20 01 121 11 13-1.5 00 00 1.50 Sample Output 0.71
0.00
0.75

Author CHEN, Yue
Source ZJCPC2004
Recommend JGShining???|???We have carefully selected several similar problems for you:??1006?1009?1005?1008?1004

HDU1007分治+遞歸

題意：

給n個點的坐標，求距離最近的一對點之間距離的一半

思路：

其實就是求最近點對的距離，主要思想就是分治
先把n個點按x坐標排序，然后求左邊n/2個和右邊n/2個的最近距離
然后合并；重點也是合并：

首先，假設點是n個，編號為0到n-1。我們要分治求，則找一個中間的編號mid，
先求出1到mid點的最近距離設為d1，還有mid+1到n的最近距離設為d2。
這里的點需要按x坐標的順序排好，并且假設這些點中，沒有2點在同一個位置。
（若有，則直接最小距離為0了）。


然后，令ans為d1, d2中較小的那個點。
如果說最近點對中的兩點都在1-mid集合中，或者mid+1到n集合中，則d就是最小距離了。
但是還有可能的是最近點對中的兩點分屬這兩個集合，所以我們必須先檢測一下這種情況是否會存在，
若存在，則把這個最近點對的距離記錄下來，去更新ans。這樣我們就可以得道最小的距離ans了。


關鍵是要去檢測最近點對，理論上每個點都要和對面集合的點匹配一次，那效率還是不能滿足我們的要求。
所以這里要優化。怎么優化呢？考慮一下，假如以我們所選的分割點mid為界，
如果某一點的橫坐標到點mid的橫坐標的絕對值超過d1并且超過d2，
那么這個點到mid點的距離必然超過d1和d2中的小者，所以這個點到對方集合的任意點的距離必然不是所有點中最小的。


所以我們先把在mid為界左右一個范圍內的點全部篩選出來，放到一個集合里。
篩選好以后，當然可以把這些點兩兩求距離去更新d了，不過這樣還是很慢，
萬一滿足條件的點很多呢。這里還得繼續優化。首先把這些點按y坐標排序。
假設排序好以后有cnt個點，編號為0到cnt-1。那么我們用0號去和1到cnt-1號的點求一下距離，
然后1號和2到cnt-1號的點求一下距離。

如果某兩個點y軸距離已經超過了ans，這次循環就可以直接break了，開始從下一個點查找了.

#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int maxn=1e5+10; struct point{ double x,y; }p[maxn]; int a[maxn]; bool cmpx(point a,point b){return a.x<b.x;}; bool cmpy(int a,int b){return p[a].y<p[b].y;}; double dis(point a,point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double find_min(int l,int r) {if(l+1==r) return dis(p[l],p[r]);//只有兩個點if(l+2==r) return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r])));//三個點int mid=(l+r)>>1;double ans=min(find_min(l,mid),find_min(mid+1,r));//檢測最近點對中的兩點分屬這兩個集合int i,j,cnt=0;for(i=l;i<=r;i++){//記錄最近點對if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)a[cnt++]=i;}sort(a,a+cnt,cmpy);for(i=0;i<cnt;i++){for(j=i+1;j<cnt;j++){//如果某兩個點y軸距離已經超過了ansif(p[a[j]].y-p[a[i]].y>=ans) break;ans=min(ans,dis(p[a[i]],p[a[j]]));}}return ans; } int main() {int n;while(scanf("%d",&n)&&n){for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}sort(p,p+n,cmpx);printf("%.2lf\n",find_min(0,n-1)/2);}return 0; }

總結

以上是生活随笔為你收集整理的HDU1007 Quoit Design 分治+递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。