题解 P2874 【[USACO07FEB]新牛棚Building A New Barn】

· · 题解

思路：

首先，我们知道两点曼哈顿距离公式：

d=|x1-x2|+|y1-y2|

　　设S为题中所求的某个点(x,y)到n个点的曼哈顿距离之和，即S=\sum{d}

　　那么有S=\sum{|x-xi|}+\sum{|y-yi|}

　　容易发现，x,y互不影响求值，于是，我们可以将本题中的横纵坐标分开各自计算。

　　这样本题就变成了一道中学数学题：求|x-x1|+|x-x2|+…|x-xn|\;min，和求|y-y1|+|y-y2|+…|y-yn|\;min

　　由中学的数学知识可知直接求中位数就行了（可以分类讨论，也可以几何意义解决）。

　　那么，我们直接对x,y各自排序：

　　 1、当n为奇数时，取x[n/2+1]和y[n/2+1]，由于题意中不能选给出的点，所以判断：

　　　　若该点为给出的点，则枚举它的上下左右四个点上能求得的最小的S，更新ans1，然后统计ans当且仅当这4个点的S=ans1;

　　　　若该点不为给出的点，则直接将ans1赋为S，ans2赋为1。

　　 2、当n为偶数时，取x[n/2],x[n/2+1]和y[n/2],y[n/2+1]，显然这(x[n/2+1]-x[n/2]+1)*(y[n/2+1]-y[n/2]+1)个点到给定的n个点的曼哈顿距离和S相等（因为这个矩形中的点的横坐标在x[n/2],x[n/2+1]之间，纵坐标也同理），于是枚举矩形中每个点是否是给定的点，求一次ans1就OK了，先让ans2等于这个矩形的点数，每次更新减小就行了。

欢迎来踩博客：five20（本人蒟蒻，写题不易，转载请注明出处）

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=1e5+7;
int n,b[N],c[N],ans1=233333333,ans2;
struct point{int x,y;}a[N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
il int gi(){
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
    return f?-a:a;
}
il int getsum(int x,int y){
    int ans=0;
    for(int i=1;i<=n;i++)ans+=abs(x-b[i])+abs(y-c[i]);
    return ans;
}
int main()
{
    n=gi();
    for(int i=1;i<=n;i++)a[i].x=b[i]=gi(),a[i].y=c[i]=gi();
    sort(b+1,b+n+1);
    sort(c+1,c+n+1);
    if(n&1){
        int x=b[(n>>1)+1],y=c[(n>>1)+1];
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            int sum=getsum(xx,yy);
            if(sum<ans1)ans1=sum,ans2=1;
            else if(sum==ans1)++ans2;
        }
    }
    else {
        int x1=b[(n>>1)+1],x2=b[n>>1],y1=c[(n>>1)+1],y2=c[n>>1];
        ans2=(x1-x2+1)*(y1-y2+1);
        ans1=getsum(x1,y1);
        for(int i=1;i<=n;i++)
            if(a[i].x>=x2&&a[i].x<=x1&&a[i].y>=y2&&a[i].y<=y1)ans2--;
    }
    cout<<ans1<<' '<<ans2;
    return 0;
}