https://www.luogu.com.cn/problem/P1429
分治法
将点对从中间分成两个集合Sl,Sr,分别递归求Sl内的最近点对,Sr内的最近点对
合并时,若Sl内部最近点对距离d1,Sr为d2
令d=min(d1,d2)
暴力算分界线往左往右d距离内的点对距离即可
这些点不会很多
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; #define N 200001 const double inf=1e11; struct node { double x,y; }e[N]; int a[N]; bool cmp(node p,node q) { return p.x<q.x; } double getdis(int p,int q) { return sqrt((e[p].x-e[q].x)*(e[p].x-e[q].x)+(e[p].y-e[q].y)*(e[p].y-e[q].y)); } double solve(int l,int r) { if(l==r) return inf; int mid=l+r>>1; double d1=solve(l,mid); double d2=solve(mid+1,r); double d=min(d1,d2); int m=0; for(int i=l;i<=r;++i) if(abs(e[i].x-e[mid].x)<=d) a[++m]=i; for(int i=1;i<m;++i) for(int j=i+1;j<=m;++j) d=min(d,getdis(a[i],a[j])); return d; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lf%lf",&e[i].x,&e[i].y); sort(e+1,e+n+1,cmp); printf("%.4lf",solve(1,n)); }
题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的
输入格式
第一行:n;2≤n≤200000
接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式
仅一行,一个实数,表示最短距离,精确到小数点后面4位。
输入输出样例
输入 #13 1 1 1 2 2 2输出 #1
1.0000
说明/提示
0<=x,y<=10^9