[HOJ] 84 - 聖誕老人送禮物

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100005
struct P{
    int x,y;
    friend bool operator < (P a,P b){
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    }
}s[N],t1,t2;
vector<int> X,Y;
vector<P> arr;
int main(){
    int n,m,i,j,t,x,y,tmp=0;
    long long int ans=0,out=10000000000000000LL;
    scanf("%d%d%d",&n,&m,&t);
    for(i=0;i<t;i++){
        scanf("%d%d",&s[i].x,&s[i].y);
        X.push_back(s[i].x);
        Y.push_back(s[i].y);
    }
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    if(t%2){
        arr.push_back((P){X[t/2],Y[t/2]});
    }
    else{
        arr.push_back((P){X[t/2],Y[t/2]});
        arr.push_back((P){X[t/2-1],Y[t/2-1]});
        arr.push_back((P){X[t/2-1],Y[t/2]});
        arr.push_back((P){X[t/2],Y[t/2-1]});
    }
    for(j=0;j<arr.size();j++){
        t1=arr[j];
        ans=0,tmp=0;
        for(i=0;i<t;i++){
            ans+=abs(s[i].x-t1.x)+abs(s[i].y-t1.y);
            ans+=abs(s[i].x-t1.x)+abs(s[i].y-t1.y);
            tmp=max(tmp,abs(s[i].x-t1.x)+abs(s[i].y-t1.y));
        }
        ans-=tmp;
        if(ans<out || ans==out && t1<t2){
            out=ans,t2=t1;
        }
    }
    printf("%lld\n%d %d\n",out,t2.x,t2.y);
}