*Part2.4 P1429 平面最近点对【平面分治】

原题链接：P1429 平面最近点对（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的

思路：平面分治，每次处理两边，再计算跨区间点对距离，贴一个优质题解(42条消息) 分治入门——平面分治_zhang_ab的博客-CSDN博客_平面分治

评价：基本分治考察

 1 #include
 2 using namespace std;
 3 //#define mod 1000000007
 4 #define inf 0x3f3f3f3f
 5 typedef long long ll;
 6 struct node
 7 {
 8     double x,y;
 9 }a[200005];
10 bool cmp(struct node e1,struct node e2)
11 {
12     return e1.x<e2.x;
13 }
14 double dis(struct node e1,struct node e2)
15 {
16     return sqrt((e1.x-e2.x)*(e1.x-e2.x)+(e1.y-e2.y)*(e1.y-e2.y));
17 }
18 double solve(int l,int r)
19 {
20     if(l==r) return inf;
21     if(l+1==r) return dis(a[l],a[r]);
22     int mid=(l+r)/2;
23     double st=a[mid].x;
24     double d=min(solve(l,mid),solve(mid+1,r));
25     for(int i=mid;i>=l&&st-a[i].x)
26         for(int j=mid+1;j<=r&&a[j].x-st)
27             d=min(d,dis(a[i],a[j]));
28     return d;
29 }
30 int main()
31 {
32     int n;
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
35     sort(a+1,a+1+n,cmp);
36     double ans =solve(1,n);
37     printf("%.4f",ans);
38 }