给定平面上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
暴力水过。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstdlib>
6 using namespace std;
7 const int MAXN=10001;
8 void read(int & n)
9 {
10 char c='+';int x=0;
11 while(c<'0'||c>'9')c=getchar();
12 while(c>='0'&&c<='9')
13 {
14 x=x*10+(c-48);
15 c=getchar();
16 }
17 n=x;
18 }
19 int n;
20 struct node
21 {
22 int x;
23 int y;
24 }a[MAXN];
25 double ans=12700000;
26 int main()
27 {
28 read(n);
29 for(int i=1;i<=n;i++)
30 {
31 read(a[i].x);
32 read(a[i].y);
33 }
34 for(int i=1;i<=n;i++)
35 {
36 for(int j=i+1;j<=n;j++)
37 {
38 double p=sqrt((fabs(a[j].x-a[i].x)*fabs(a[j].x-a[i].x))+(fabs(a[j].y-a[i].y)*fabs(a[j].y-a[i].y)));
39 if(p<ans)
40 ans=p;
41 }
42 }
43 printf("%.4lf",ans);
44 return 0;
45 }