poj 3269 Building A New Barn

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn=1e4+9;

int x[maxn],y[maxn];

struct D

{

    int x,y;

    bool operator <(const D &xx)const

    {

        if(x==xx.x)

        return y<xx.y;

        return x<xx.x;

    }

}point[maxn];

int abs(int a)

{

    if(a<0) return -a;

    return a;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int n;

    scanf("%d",&n);

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

    {

        scanf("%d %d",&x[i],&y[i]);

        point[i].x=x[i];

        point[i].y=y[i];

    }

    sort(x+1,x+1+n);

    sort(y+1,y+1+n);

    sort(point+1,point+1+n);

    int ans=0;

    long long sum=0;

    if(n&1||(x[n>>1]==x[n+2>>1]&&y[n>>1]==y[n+2>>1]))

    {

        bool flag=false;

        int xx=x[n+1>>1],yy=y[n+1>>1];

        for(int k=1;k<=n;k++)

        if(point[k].x==xx&&point[k].y==yy)

        flag=true;

        if(!flag)

        {

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

            {

                sum+=abs(x[i]-xx);

                sum+=abs(y[i]-yy);

            }

            printf("%lld %d\n",sum,1);

        }

        else

        {

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

            {

                sum+=abs(x[i]-(xx+1));

                sum+=abs(y[i]-yy);

            }

            long long ret=sum,tmp=1;

            sum=0;

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

            {

                sum+=abs(x[i]-(xx-1));

                sum+=abs(y[i]-yy);

            }

            if(sum==ret) tmp++;

            else if(sum<ret) ret=sum;

            sum=0;

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

            {

                sum+=abs(x[i]-xx);

                sum+=abs(y[i]-(yy+1));

            }

            if(sum==ret) tmp++;

            else if(sum<ret) ret=sum;

            sum=0;

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

            {

                sum+=abs(x[i]-xx);

                sum+=abs(y[i]-(yy-1));

            }

            if(sum==ret) tmp++;

            else if(sum<ret) ret=sum;

            printf("%lld %d\n",sum,tmp);

        }

    }

    else

    {

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

        {

            sum+=abs(x[i]-x[n>>1]);

            sum+=abs(y[i]-y[n>>1]);

        }

        int k=1;

        for(int i=x[n>>1];i<=x[n+2>>1];i++)

        for(int j=y[n>>1];j<=y[n+2>>1];j++)

        {

            for(;point[k].x<i||(point[k].x==i&&point[k].y<j);k++);

            if(point[k].x!=i||point[k].y!=j) ans++;

        }

        printf("%lld %d\n",sum,ans);

    }

    return 0;

}