P1429 平面最近点对(加强版)

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

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

 

第一行:n;2≤n≤200000

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
3
1 1
1 2
2 2
输出样例#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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:二维计算几何模板

下一篇:1570. [POJ3461]乌力波