描述

   在一块地上,有着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
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             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\n",no1,no2);36     return 0; 37 }
           
          
         
        
       

到后面数据可能很大

用勾股定理算出来的数可能存不下

可以在算的时候把横坐标纵坐标同时除以100.0，利用精度代替位数

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

不用分治！！！