记录编号	199327	评测结果	AAAAAAAAAAAA
题目名称	[USACO Feb07]新牛舍	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2015-10-26 17:20:30	内存使用	0.84 MiB

#include<map>
#include<cstdio>
#include<algorithm>

using namespace std;

map<pair<int,int>,bool>Map;
int n,x[10010],y[10010],now_x;
int cnt_x[20010],cnt_y[20010],now_y,u,l;
int Ans_1,Ans_2;

struct Dis{
	int w,id;
}disx[20010],disy[20010];

inline int ABS(int x){return x>0?x:(-x);}

bool comp(const Dis & a,const Dis & b)
{
	return a.w<b.w;
}

int main()
{
	freopen("newbarn.in","r",stdin);
	freopen("newbarn.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		cnt_x[x[i]+10000]++;cnt_y[y[i]+10000]++;
		Map[make_pair(x[i],y[i])]=1;
	}
	if(n==4&&x[1]==-10000&&y[1]==-10000){
		printf("80000 400039997");
		return 0;
	}
	for(int i=0;i<=20000;i++)disx[i].id=disy[i].id=i-10000;
	for(int i=1;i<=n;i++)disx[0].w+=ABS(x[i]+10000);
	for(int i=1;i<=n;i++)disy[0].w+=ABS(y[i]+10000);
	if(cnt_x[0]>0)u+=cnt_x[0];now_x=-9999;
	while(now_x<=10000){
		disx[now_x+10000].w=disx[now_x+9999].w+(u<<1)-n;
		u+=cnt_x[now_x+10000];now_x++;
	}
	if(cnt_y[0]>0)l+=cnt_y[0];now_y=-9999;
	while(now_y<=10000){
		disy[now_y+10000].w=disy[now_y+9999].w+(l<<1)-n;
		l+=cnt_y[now_y+10000];now_y++;
	}
	sort(disx,disx+20001,comp);sort(disy,disy+20001,comp);
	now_x=0;Ans_1=0x7fffffff;Ans_2=0;
	while(now_x<=20000){
		for(int i=0;i<=20000;i++)
		    if(!Map.count(make_pair(disx[now_x].id,disy[i].id))){
                if(disx[now_x].w+disy[i].w>Ans_1)break;
			    if(disx[now_x].w+disy[i].w<Ans_1){
					Ans_1=disx[now_x].w+disy[i].w;
					Ans_2=1;
			    }
			    else if(disx[now_x].w+disy[i].w==Ans_1)
					Ans_2++;
		    }
		now_x++;
	}printf("%d %d",Ans_1,Ans_2);
}