【Tyvj1081】最近距离

2014-05-23
竞赛题解 / 模拟
tyvj

描述 Description

在一块地上, 有着 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

输入格式 InputFormat

第一行 n。
下面 n 行，x,y。

输出格式 OutputFormat

最近的两个点

样例输入 SampleInput

25
24804 7918
98983 95075
10819 48641
84481 33476
56724 20854
83193 17014
72997 5394
69263 33045
26810 75288
85442 47243
81678 82129
84199 35206
68212 77035
62113 87896
49538 1375
145 90953
58175 62546
73175 5853
7789 37961
18883 49418
78257 90342
2048 64282
49057 95081
89406 47329
9778 68104

样例输出 SampleOutput

7 18

来源 Source

usaco nov09 cu 第三道

Tyvj 1081

代码 Code

水。精度问题略坑。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/2711
struct point
{
    double z,y,x;
};
point a[10000];
int i,j,n,m,l,r;
double t,k,sd;
double dis(point a,point b)
{
    double tx,ty;
    tx=a.x-b.x;
    ty=a.y-b.y;
    return sqrt(tx*tx+ty*ty);
}
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
    sd=inf;
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (i!=j)
    {
        t=dis(a[i],a[j]);
        if (sd>t)
        {
            sd=t;
            l=i;r=j;
        }
    }
    printf("%d %d\n",l,r);
    return 0;
}