平面最近点对/最远点对
Bamboo之吃我一拳(单纯的平面最近点对)
零崎的战争（两个点集的平面最近点对）
#include <iostream> #include <algorithm> #include <cmath> using namespace std; const double eps = 1e-6; const int maxn = 100010; const double INF = 1e20; struct point{ double x,y; bool flag; }; double dist(point a,point b){ return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } point p[maxn] , temp[maxn]; bool cmpxy(point a,point b){ if(a.x != b.x) return a.x<b.x; else return a.y < b.y; } bool cmpy(point a,point b){ return a.y < b.y; } double Closest_Pair(int left,int right){ if(left == right) return INF; if(left+1 == right){ if(p[left].flag != p[right].flag) return dist(p[left],p[right]); else return INF; } int mid=(left+right)/2; double d=min(Closest_Pair(left,mid),Closest_Pair(mid+1,right)); int k=0; for(int i=left;i<=right;i++){ if(fabs(p[mid].x - p[i].x) <=d ) temp[k++]=p[i]; } sort(temp,temp+k,cmpy); for(int i=0;i<k;i++) for(int j=i+1;j<k && temp[j].y-temp[j].y<d;j++) if(temp[i].flag != temp[j].flag) d=min(d,dist(temp[i],temp[j])); return d; } int main(){ int n,K; scanf("%d",&K); while(K--){ scanf("%d",&n); for(int i=0;i<2*n;i++){ scanf("%lf %lf",&p[i].x,&p[i].y); if(i<n) p[i].flag=true; else p[i].flag=false; } sort(p,p+n*2,cmpxy); printf("%.3lf ",Closest_Pair(0,2*n-1)); } return 0; }
平面最近点对实质上体现的还是分治的思想
利用二分法将一个点集划分为两部分，那么平面最近点对只会存在于两个几何内部 或者在区间之间。
利用递归计算出两个内部的最近距离之后，利用当前距离为标杆，控制判断区间之间的最近距离（剪枝后的遍历）最后返回答案即可。
两个点集的最近点对，可以在原有代码的基础上增加区别集合与集合的falg 标示位，在计算距离之前，判断下这两个点是否在不同集合即可。
寻找最远点对(单纯的平面最近点对)
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> using namespace std; struct Point { int x,y; Point(int _x = 0,int _y = 0) { x = _x; y = _y; } Point operator -(const Point &b)const { return Point(x - b.x, y - b.y); } int operator ^(const Point &b)const { return x*b.y - y*b.x; } int operator *(const Point &b)const { return x*b.x + y*b.y; } void input() { scanf("%d%d",&x,&y); } }; //距离的平方 int dist2(Point a,Point b) { return (a-b)*(a-b); } //******二维凸包，int*********** const int MAXN = 50010; Point list[MAXN]; int Stack[MAXN],top; bool _cmp(Point p1,Point p2) { int tmp = (p1-list[0])^(p2-list[0]); if(tmp > 0)return true; else if(tmp == 0 && dist2(p1,list[0]) <= dist2(p2,list[0])) return true; else return false; } void Graham(int n) { Point p0; int k = 0; p0 = list[0]; for(int i = 1;i < n;i++) if(p0.y > list[i].y || (p0.y == list[i].y && p0.x > list[i].x)) { p0 = list[i]; k = i; } swap(list[k],list[0]); sort(list+1,list+n,_cmp); if(n == 1) { top = 1; Stack[0] = 0; return; } if(n == 2) { top = 2; Stack[0] = 0; Stack[1] = 1; return; } Stack[0] = 0; Stack[1] = 1; top = 2; for(int i = 2;i < n;i++) { while(top > 1 && ((list[Stack[top-1]]-list[Stack[top-2]])^(list[i]-list[Stack[top-2]])) <= 0) top--; Stack[top++] = i; } } //旋转卡壳，求两点间距离平方的最大值 int rotating_calipers(Point p[],int n) { int ans = 0; Point v; int cur = 1; for(int i = 0;i < n;i++) { v = p[i]-p[(i+1)%n]; while((v^(p[(cur+1)%n]-p[cur])) < 0) cur = (cur+1)%n; ans = max(ans,max(dist2(p[i],p[cur]),dist2(p[(i+1)%n],p[(cur+1)%n]))); } return ans; } Point p[MAXN]; int main() { int n; while(scanf("%d",&n) == 1) { for(int i = 0;i < n;i++)list[i].input(); Graham(n); for(int i = 0;i < top;i++)p[i] = list[Stack[i]]; printf("%d ",rotating_calipers(p,top)); } return 0; }
kuangbin 大大的板子（侵删）
这道题首先可以确认的是最远点对一定在凸包上。
求出凸包以后，作两点的平行线，当一点到平行线的方向发生改变时达到可能的最大值（旋转卡壳）。然后旋转到每个点都考虑完毕就可以了。