首页 > > 程序设计 > C/C++ >

P1429 平面最近点对（加强版）

2018-06-17 22:03:19来源：未知阅读 ()

题目描述

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

输入输出格式

输入格式：

第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式：

仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例

输入样例#1：

输出样例#1：

1.0000

说明

0<=x,y<=10^9

实在想不明白这题跟计算几何有什么关系，，

不过也算是一道好题，

?将各个点（结构体）按x的从小到大排序

?首先运用二分思想将点集合分到最后只剩两个点的时候

?然后用这两点之间的距离更新答案（答案初始化为无限大）

?然后我们要找到二分的具体实现方案——每次分到一些点时，找到这些点标号的中间（因为点都排好序了，所以其实也就是找到x轴上一条分界线），将整个点的集合大致均分为两个部分

?在分界线的右侧，将与分界线的距离小于ans的点纳入到一个辅助结构体里面

?在分界线的左侧，不断枚举点，枚举到离分界线小于ans的点时，与辅助结构体中的点挨个（等会有解释）判断其距离有没有小于ans，更新ans

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=200001;
 7 inline void read(int &n)
 8 {
 9     char c=getchar();bool flag=0;n=0;
10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
11     while(c>='0'&&c<='9')    n=n*10+(c-48),c=getchar();if(flag==1)n=-n;
12 }
13 struct Point
14 {
15     double x,y;
16 }point[MAXN],a[MAXN];
17 int comp(const Point &a,const Point &b)
18 {return (a.x==b.x)?a.y<b.y:a.x<b.x;}
19 double ans=43843843800.0;
20 void work(int l,int r)
21 {
22     if(l==r)    return ;
23     int mid=(l+r)>>1;
24     work(l,mid);work(mid+1,r);
25     int t=0;
26     for(int i=mid+1;i<=r;i++)
27         if(point[i].x-point[mid].x<ans)
28             a[++t]=point[i];
29     for(int i=l;i<=mid;i++)
30         if(point[mid].x-point[i].x<=ans)
31             for(int k=1;k<=t;k++)
32                 ans=min(ans,(double) sqrt( (point[i].x-a[k].x)*(point[i].x-a[k].x)+(point[i].y-a[k].y)*(point[i].y-a[k].y) ));
33 }
34 int main()
35 {
36     int n;
37     read(n);
38     for(int i=1;i<=n;i++)        scanf("%lf%lf",&point[i].x,&point[i].y);
39     sort(point+1,point+n+1,comp);
40     work(1,n);
41     printf("%.4lf",ans);
42     return 0;
43 }