Bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍中位数,数学

1696: [Usaco2007 Feb]Building A New Barn新牛舍

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 394 Solved: 181
[Submit][Status][Discuss]

Description

经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃草位置，所以他想把牛舍造在最方便的地方。每一头牛吃草的位置是一个整数点(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000)。没有两头牛的吃草位置是相邻的。 JOHN决定把牛舍造在一个没有牛吃草的整数点上。如果牛舍在(X, Y)，在(X_i, Y_i)的牛到牛舍的距离是|X-X_i|+|Y-Y_i|。 JOHN把牛舍造在哪儿才能使所有牛到牛舍的距离和最低？

Input

第1行：一个数，N。

第2~N+1行：第i+1行包含第i头牛的位置(X_i, Y_i)。

Output

第1行：两个数，最小距离和和所有可能达到这个距离和的牛舍位置的数目。

Sample Input

4
1 -3
0 1
-2 1
1 -1

输入解释：

一共有4头牛，位置分别为(1, -3), (0, 1), (-2, 1), 和(1, -1).

Sample Output

10 4

输出解释：
最小距离和是10，可以在牛舍位于 (0, -1), (0, 0), (1, 0), (1, 1)时达到。

HINT

Source

Gold

题解：

由于题目要求总距离最小，所以就可以想到找中位数。

然而证明并不会。。。自己找度娘。。。

把x，y分别排序。

如果牛的个数为奇数，我们就分别取x,y排好序的中点。然后判断是否有牛。若没有就取当前这个点，若有就去找上下左右四个点中最小值和最小值的个数。(题目保证了牛不相邻)

如果为偶数，中位数有两个(x1,y1),(x2,y2)。则答案的个数为(x2-x1+1)*(y2-y1+1)-中间有牛的个数。

具体看程序：

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 1e9

 int x[],y[],xx[],yy[];

 int fx[]={,,,-};

 int fy[]={,-,,};

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 int main()

 {

     freopen("newbarn.in","r",stdin);

     freopen("newbarn.out","w",stdout);

     int n,i,nn,x1,y1,x2,y2,sum,j,gs,mn;

     n=read();

     for(i=;i<=n;i++)x[i]=read(),y[i]=read(),xx[i]=x[i],yy[i]=y[i];

     sort(xx+,xx+n+);

     sort(yy+,yy+n+);

     if(n%!=)

     {

         nn=(n+)/;

         x1=xx[nn];

         y1=yy[nn];

         for(j=;j<=n;j++)if(x[j]==x1&&y[j]==y1)break;

         if(j<=n)

         {

             mn=INF;gs=;

             for(i=;i<=;i++)

             {

                 x2=x1+fx[i];

                 y2=y1+fy[i];

                 sum=;

                 for(j=;j<=n;j++)

                 {

                     sum+=(int)fabs(x[j]-x2)+(int)fabs(y[j]-y2);

                 }

                 if(sum<mn)

                 {

                     mn=sum;gs=;

                 }

                 else if(sum==mn)gs++;

             }

             printf("%d %d",mn,gs);

             return ;

         }

         sum=;

         for(i=;i<=n;i++)

         {

             sum+=(int)fabs(x[i]-x1)+(int)fabs(y[i]-y1);

         }

         printf("%d 1",sum);

     }

     else

     {

         nn=n/;

         sum=;

         x1=xx[nn];

         y1=yy[nn];

         sum=;

         for(i=;i<=n;i++)

         {

             sum+=(int)fabs(x[i]-x1)+(int)fabs(y[i]-y1);

         }

         x2=xx[nn+];

         y2=yy[nn+];

         gs=(x2-x1+)*(y2-y1+);

         for(i=;i<=n;i++)

         {

             if(x[i]>=x1&&x[i]<=x2&&y[i]>=y1&&y[i]<=y2)

             {

                 gs--;

             }

         }

         printf("%d %d",sum,gs);

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }

牛舍