最近点对问题，将这些点全部映射到第一象限，题目的这个距离其实就是最短路径距离的平方，暴力的情况下，最后一定会超时爆掉，只能使用分治法。
//分治法 #include<iostream> #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; #define sc scanf #define ci cin #define co cout #define e endl #define lld long long int #define Maxx(a,b) (a>b?a:b) #define Minn(a,b) (a<b?a:b) #define maxn 100005 #define infinite 2000000000001 struct Point{ int x,y; }point[maxn]; int tmp[maxn]; bool cmp(Point po1,Point po2){//由x递增排序，x相同由y递增排序 if(po1.x == po2.x){ if(po1.y < po2.y) return 1; else return 0; }else{ if(po1.x < po2.x) return 1;//点1的x比点2的x小就没问题，否则就要交换位置 else return 0; } } bool cmp1(int a,int b){ if(point[a].y < point[b].y) return 1; return 0; } lld getDis(int x1,int y1,int x2,int y2){ lld tmp1 = (lld)(x1 - x2); tmp1 = tmp1 * tmp1; lld tmp2 = (lld)(y1 - y2); tmp2 = tmp2 * tmp2; return tmp1+tmp2; } lld devide(int left,int right){//分治法nlogn lld distance = infinite; if(left == right){ return distance; }else if(left == right-1){ return getDis(point[left].x,point[left].y,point[right].x,point[right].y); }else{ int mid = (left + right)/2; lld dis1 = devide(left,mid); lld dis2 = devide(mid+1,right); distance = Minn(dis1,dis2);//co<<distance<<e; int cnt = 1; for(int i=left;i<=right;i++){ if(abs(point[i].x-point[mid].x) <= sqrt(distance)){ //极端情况第一次划分，所有的点都位于同一x值上,10的六次方全在 point[mid].x上 tmp[cnt++] = i; } } sort(tmp+1,tmp+cnt,cmp1);//把这些数按y的大小来排 16*10^5 int i,j; for(i=1;i<cnt;i++){//10^5 for(j=i+1;(point[tmp[j]].y-point[tmp[i]].y<=sqrt(distance))&&j<cnt;j++){//玄学的关键，因为之前已经对这个数按y排序过了，这些数代表点对的序号，先定下一个点，另一个点的距离只要和定点的距离超过最小距离，直接就结束第二重循环了，至于复杂度是多少，就是玄学了 dis1 = getDis(point[tmp[i]].x,point[tmp[i]].y,point[tmp[j]].x,point[tmp[j]].y); distance = Minn(dis1,distance); } } return distance; } } int main(){ int n; lld distance; while(sc("%d",&n)!=EOF){ distance = infinite; for(int i=1;i<=n;i++){ ci>>point[i].x; ci>>point[i].y; point[i].x = abs(point[i].x); point[i].y = abs(point[i].y); } sort(point + 1,point + n + 1,cmp); co<<devide(1,n)<<e; } return 0; } //暴力 #include<iostream> #include<stdio.h> #include<math.h> using namespace std; #define sc scanf #define ci cin #define co cout #define e endl #define lli long long int #define maxn 100000 lli dis(int x1,int y1,int x2,int y2){ //Y距离(x1+x3)*(x1+x3) + (y1+y3)*(y1+y3) x2 = -x3 y2 = -y3 //可以等价看作为两点之间最短距离 (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2); //查找两点最小距离，将点(x1,y1),(x2,y2)都划到第一象限以及x轴正半轴和y轴正半轴上 //在第一象限取一个点A，在四个象限里分别取B1,B2,B3,B4四个点为对称点，A点必然和同一象限里的B1点距离最近,当A为原点时和所有点距离相等 x1 = abs(x1);//co<<x1<<e; y1 = abs(y1);//co<<y1<<e; x2 = abs(x2);//co<<x2<<e; y2 = abs(y2);//co<<y2<<e; lli tmp1 = (lli)(x1-x2);//co<<tmp1<<e; tmp1 = tmp1 * tmp1; lli tmp2 = (lli)(y1-y2);//co<<tmp2<<e; tmp2 = tmp2 * tmp2; lli distanceS = tmp1 + tmp2; //co<<distanceS<<e; return distanceS; } int main(){ lli tmp = 0,distanceS;//默认为最大距离：原点和(10^6,10^6)的距离=2*10^12 int x[maxn],y[maxn]; int n; while(sc("%d",&n)!=EOF){ distanceS = 2*1000000000000; for(int i=1;i<=n;i++){//O(n) 100000 ci>>x[i]; ci>>y[i]; } for(int i=1;i<=n;i++){//O((n+1)*n/2) 5000150000 for(int j=i+1;j<=n;j++){ tmp = dis(x[i],y[i],x[j],y[j]); if(tmp<distanceS) distanceS = tmp; } }//最坏情况100000+500000500000=5000150000 co<<distanceS<<e; } return 0; }
