「JoyOI1081」最近距离
题目描述
在一块地上,有着n(1<=n<=2000) 头牛,输入n,再分别输入这n头牛的坐标(x,y)
(1<=x<=100000,1<=y<=100000),如果第i头牛与第j头牛间的距离最近,那么输出i和j
10 | . . . . . . . 3 . . . . .
9 | . 1 . . 2 . . . . . . . .
8 | . . . . . . . . . . . . .
7 | . . . . . . . . . . 4 . .
6 | . . . . . . 9 . . . . . .
5 | . 8 . . . . . . . . . . .
4 | . . . . . 7 . . . . . . .
3 | . . . . . . . . . 5 . . .
2 | . . . . . . . . . . . . .
1 | . . . . 6 . . . . . . . .
0 —————————
1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3
输入
第一行n 下面n行,x,y
输出
最近的两个点
样例输入
9 2 9 5 9 8 10 11 7 10 3 5 1 6 4 2 5 7 6
样例输出
7 9
提示
usaco nov09 cu 第三道
代码
坐标可能是实数。。。
WTF
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<iostream> #include<cmath> #include<cstdio> using namespace std; int n,ansi,ansj; double x[2001],y[2001],mn=9999999; double dis(int a,int b) { return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(dis(i,j)<mn){mn=dis(i,j);ansi=i;ansj=j;} printf("%d %d",ansi,ansj); return 0; } |
Subscribe