想法：
- 將所有點依x座標排序
- 從中間切開，將所有點分成左右兩個集合(設line為中線x座標)
- 左右兩邊各求出任兩點最小值a,b，設d為min(a,b)
- 那麼現在只要枚舉(line+-d)這範圍內的點有沒有比d還更小的值即可
遞迴定義：
- divide(point_type a[], low, high)
- 求出a[low]~a[high]範圍內任兩點的最短距離
- combine(point_type a[], low, mid, high, min_left, min_right)
- d=min(min_left,min_right)
- line=(a[mid].x+a[mid+1].x)/2
- 合併左右兩個集合，並確認在(line+-d)的範圍內有沒有比d更小的值，最後回傳最小值
更詳細圖解可參考KuoE0:http://www.slideshare.net/KuoE0/acmicpc-uva10245
注意輸入輸出皆要用double
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| #include <cmath> | |
| using namespace std; | |
| struct point_type{ | |
| double x; | |
| double y; | |
| }; | |
| bool cmp(point_type a,point_type b) | |
| { | |
| return a.x<b.x; | |
| } | |
| double distance(point_type a,point_type b); | |
| double divide(point_type a[],int low,int high); | |
| double combine(point_type a[],int low,int mid,int high,double min_left,double min_right); | |
| int main() | |
| { | |
| int N; | |
| point_type point[10001]; | |
| while(scanf("%d",&N)) | |
| { | |
| if (N==0) break; | |
| for(int i=0;i<N;i++) | |
| scanf("%lf %lf",&point[i].x,&point[i].y); | |
| sort(point,point+N,cmp); | |
| double dis=divide(point,0,N-1); | |
| if(dis>=10000.0) printf("INFINITY\n"); | |
| else printf("%.4lf\n",dis); | |
| } | |
| return 0; | |
| } | |
| double Distance(point_type a,point_type b) | |
| { | |
| return (double)sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)); | |
| } | |
| double divide(point_type a[],int low,int high) | |
| { | |
| if(low>=high) return 99999; //切到只剩1個點，return inf | |
| int mid=(low+high)/2; | |
| double min_left=divide(a,low,mid); | |
| double min_right=divide(a,mid+1,high); | |
| return combine(a,low,mid,high,min_left,min_right); | |
| } | |
| double combine(point_type a[],int low,int mid,int high,double min_left,double min_right) | |
| { | |
| double d=(min_left<min_right)?min_left:min_right; | |
| double line=(double)(a[mid].x+a[mid+1].x)*0.5; //line:左集合與右集合的中間線x座標 | |
| double min_D=d; | |
| for(int i=mid+1;a[i].x<line+d && i<=high;i++){ //枚舉line+-d範圍內左右集合的點 | |
| for(int j=mid;a[j].x>line-d && j>=low;j--){ | |
| double temp=Distance(a[i],a[j]); | |
| if(temp<min_D) min_D=temp; | |
| } | |
| } | |
| return min_D; | |
| } |
沒有留言:
張貼留言