TYVJ P1081 最近距离 Label:这不是分治！！！

描述

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

输出格式

测试样例1

输入

9
2 9
5 9
8 10
11 7
10 3
5 1
6 4
2 5
7 6

输出

7 9

备注

usaco nov09 cu 第三道

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 struct cc{
 8     double x,y;
 9 }node[2005];
10 long long N,no1,no2;
11 double ans=double(1<<30),t;
12 double dist(int i,int j){
13     return fabs(  (node[i].x-node[j].x)*(node[i].x-node[j].x) + 
14                   (node[i].y-node[j].y)*(node[i].y-node[j].y) );
15 }
16 
17 int main(){
18     scanf("%d",&N);
19     for(int i=1;i<=N;i++){
20         scanf("%lf %lf",&node[i].x,&node[i].y);
21         node[i].x/=100.0;
22         node[i].y/=100.0;
23     }
24     for(int i=1;i<=N;i++){
25         for(int j=i+1;j<=N;j++){
26             t=dist(i,j);
27             if(ans>t){
28                 ans=t;
29                 no1=i;
30                 no2=j;
31             }
32         }
33     }
34     if(no1>no2) swap(no1,no2);
35     printf("%lld %lld
",no1,no2);
36     return 0; 
37 }

到后面数据可能很大
用勾股定理算出来的数可能存不下
可以在算的时候把横坐标纵坐标同时除以100.0，利用精度代替位数

看了题解发现只有2k头牛，也就是说，连优化都不用，直接搜索！！！

不用分治！！！