网站备案主办单位性质,村级网站建设 不断增强,上海城乡建设部网站,网站服务器要求题目描述
给定平面上n个点#xff0c;找出其中的一对点的距离#xff0c;使得在这n个点的所有点对中#xff0c;该距离为所有点对中最小的。
输入格式
第一行一个整数 n#xff0c;表示点的个数。
接下来 n 行#xff0c;每行两个实数 x,y #xff0c;表示一个点的行…题目描述
给定平面上n个点找出其中的一对点的距离使得在这n个点的所有点对中该距离为所有点对中最小的。
输入格式
第一行一个整数 n表示点的个数。
接下来 n 行每行两个实数 x,y 表示一个点的行坐标和列坐标。
输出格式
仅一行一个实数表示最短距离四舍五入保留 4 位小数。
样例
样例输入 #1
3
1 1
1 2
2 2样例输出 #1
1.0000数据范围与提示
对于 100% 的数据保证0n10000 0x,y1000000000,小数点后的数字个数不超过6 。
代码
#includebits/stdc.h
using namespace std;
int n;
struct point{double x,y;
};
point a[10010],tmp[10010];
double ans;
bool cmpx(const point A,const point B){if(A.xB.x)return A.yB.y;elsereturn A.xB.x;
}
bool cmpy(const point A,const point B){if(A.yB.y)return A.xB.x;elsereturn A.yB.y;
}
double dist(point A,point B){return sqrt((A.x-B.x)*(A.x-B.x)(A.y-B.y)*(A.y-B.y));
}
double f(int L,int R){double ans218;if(LR)return ans;else if(L1R){return dist(a[L],a[R]);}else{int mid(LR)1;double ans1f(L,mid);double ans2f(mid1,R);
// coutans1 ans2endl; ansmin(ans1,ans2);
// ansans1;
// if(ansans2)
// ansans2;int cnt0;for(int iL;iR;i)if (fabs(a[i].x-a[mid].x)ans)tmp[cnt]a[i];sort(tmp1,tmpcnt1,cmpy);for(int i1;icnt;i)for(int ji1;jcnt;j)if(tmp[j].y-tmp[i].yans)ansmin(ans,dist(tmp[i],tmp[j]));return ans;}
}
int main() {cinn;for(int i1;in;i)cina[i].xa[i].y;sort(a1,an1,cmpx);//for(int i1;in;i)//couta[i].x a[i].yendl;ansf(1,n);coutfixedsetprecision(4)ansendl;//print(%.4lf\n,ans);return 0;
}
