[HOJ] 84 聖誕老人送禮物

找到中位數後找中位數離的最遠點，讓他只要走一次
若有偶數個點要四個X Y值都考慮

#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAX 100005
using namespace std;
int x[MAX],y[MAX],w,h,n,mid,l,r;
struct node{
    int x,y;
}a[MAX];
long long ans=10e18,ma,tmp,now;
long long check(int k,int m){
    ma=now=0;
    for(int i=0;i<n;i++){
        now+=(long long)(abs(x[k]-a[i].x)+abs(y[m]-a[i].y))*2;
        ma=max(ma,(long long)abs(x[k]-a[i].x)+abs(y[m]-a[i].y));
    }
    return now-ma;
}
int main(){
    scanf("%d%d%d",&w,&h,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x[i],&y[i]);
        a[i]=node{x[i],y[i]};
    }
    mid=n>>1;
    sort(x,x+n);
    sort(y,y+n);
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            tmp=check(mid-i,mid-j);
            if(tmp<ans||(tmp==ans&&(mid-i<l||(mid-i==l&&mid-j<r)))){
                ans=tmp;
                l=mid-i;
                r=mid-j;
            }
        }
    }
    printf("%lld\n%d %d\n",ans,x[l],y[r]);
}