題目鏈接：點擊查看

題目大意：給出兩個含有n個點的集合，在兩個集合中分別任選一點，使得這兩個點之間的距離最小

題目分析：因為n給到了1e5，所以n*n的暴力肯定是不行了，直接從網上copy了個分治優化的模板，時間復雜度為nlogn，可以求出n個點中相距最近的兩個點的距離，對于這個題目而言，我們將兩個集合中的點分個類，在求距離的時候，若是同類的點，直接返回無窮大即可，這樣同類的點肯定不可能是答案了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;struct Point {double x,y;bool flag; }point[N];int y_sort[N];int cmpx(Point a,Point b)//按照x對這些點從小到大排序 {return a.x<b.x; }int cmpy(int a,int b)//對最近點算法中的y_sort數組排序 {return point[a].y<point[b].y; }double dis(Point a,Point b) {if(a.flag!=b.flag)return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));return 1e20; } /*最近點對算法,在point[first]--point[last]個點中尋找一個最短距離使用該算法前先對這些點排序sort(point,point+n,cmpx); */ double findMin(int first, int last) {if((last-first)==1)return dis(point[first],point[last]);else if(last-first==2){double d1 = dis(point[first],point[first+1]);double d2 = dis(point[first],point[first+2]);double d3 = dis(point[first+1],point[first+2]);return min(min(d1,d2),d3);}//二分int mid = (first+last)/2;double min_dist = min(findMin(first,mid),findMin(mid+1,last));if(min_dist==0)return 0;int y_end = 0;for(int i=mid;point[mid].x-point[i].x<min_dist&&i>=first;i--)y_sort[y_end++]=i;for(int i=mid+1;point[i].x-point[mid+1].x<min_dist&&i<=last;i++)y_sort[y_end++]=i;sort(y_sort,y_sort+y_end,cmpy);for(int i=0;i<y_end;i++)for(int j=i+1;j<y_end&&(point[y_sort[j]].y-point[y_sort[i]].y)<min_dist;j++)min_dist=min(min_dist,dis(point[y_sort[i]],point[y_sort[j]]));return min_dist; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lf%lf",&point[i].x,&point[i].y);point[i].flag=true;}for(int i=n;i<2*n;i++){scanf("%lf%lf",&point[i].x,&point[i].y);point[i].flag=false;}sort(point,point+2*n,cmpx);printf("%.3f\n",findMin(0,2*n-1));}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3714 Raid(平面最近点对模板题，几何)的全部內容，希望文章能夠幫你解決所遇到的問題。

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