2351304_ac_30ms_220k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>

using namespace std;
int n;
typedef struct node
{
	int no;
}num;
int Num[10001][2];
num x[10001], y[10001];
bool cmp(num a, num b)
{
	return a.no<b.no;
}

int exist(int x,int y)
{
	for(int i = 0; i < n; i++)
		if(x==Num[i][0]&&y==Num[i][1])
			return 1;
	return 0;
}

int main()
{
	int no;
	int i, xx, yy;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&x[i].no,&y[i].no);
		Num[i][0] = x[i].no,Num[i][1] = y[i].no;
	}
	sort(x,x+n,cmp);sort(y,y+n,cmp);
	int ans = 0;
	for(i = 0; i < n; i++)
		ans += abs(x[n/2].no-x[i].no)+abs(y[n/2].no-y[i].no);
	if(n%2==0)
	{
		xx = x[n/2].no - x[n/2-1].no+1;
		yy = y[n/2].no - y[n/2-1].no+1;
		no = xx*yy;
		if(exist(x[n/2].no,y[n/2].no))
			no--;
		if(yy!=1&&exist(x[n/2].no,y[n/2-1].no))
			no--;
		if(xx!=1)
		{
			if(exist(x[n/2-1].no,y[n/2].no))
				no--;
			if(yy!=1&&exist(x[n/2-1].no,y[n/2-1].no))
				no--;
		}
		printf("%d %d\n",ans,no);
	}
	else
	{
		no  = 0;
		xx = yy = 1;
		if(exist(x[n/2].no,y[n/2].no))
		{
			ans = 100000;
			int tmp = 0;
			if(!exist(x[n/2].no-1,y[n/2].no))
			{
				for(i = 0; i < n; i++)
					tmp+=abs(x[n/2].no-1-x[i].no)+abs(y[n/2].no-y[i].no);
				if(tmp<ans)
					no = 1,ans = tmp;
				else
					if(tmp==ans)
						no++;
			}
			if(!exist(x[n/2].no+1,y[n/2].no))
			{
				tmp = 0;
				for(i = 0; i < n; i++)
					tmp+=abs(x[n/2].no+1-x[i].no)+abs(y[n/2].no-y[i].no);
				if(tmp<ans)
					no = 1,ans = tmp;
				else
					if(tmp==ans)
						no++;
			}
			if(!exist(x[n/2].no,y[n/2].no-1))
			{
				tmp = 0;
				for(i = 0; i < n; i++)
					tmp+=abs(x[n/2].no-x[i].no)+abs(y[n/2].no-1-y[i].no);
				if(tmp<ans)
					no = 1,ans = tmp;
				else
					if(tmp==ans)
						no++;
			}
			if(!exist(x[n/2].no,y[n/2].no+1))
			{
				tmp = 0;
				for(i = 0; i < n; i++)
					tmp+=abs(x[n/2].no-x[i].no)+abs(y[n/2].no+1-y[i].no);
				if(tmp<ans)
					no = 1,ans = tmp;
				else
					if(tmp==ans)
						no++;
			}
			printf("%d %d\n",ans,no);
		}		
	}
	return 1;
}