PKU3269: Building A New Barn

解法が面白かったのであげておきます。

概要

n個の点(n<=10000)が与えられる。ここには牛がいる。ぜんぶ整数座標である。
ある点を定めて小屋を置く。牛がいるところには小屋は置けない。一番いい場所というのは、小屋とそれぞれの牛たちのマンハッタン距離の和が最小になる点である。
一番いい小屋の位置においたときのマンハッタン距離の和とその小屋のおける場所の数を出力せよ。

解法

x,yは独立に考えることのできる場所があります。ここらへんです。
まず一番いい位置は牛と小屋の重なりを考えないと
nが奇数ならx,yはそれぞれ中央値、
nが偶数ならx,yはそれぞれ中央値2つのあいだならどこでもよいです
(JOI2011本選4を参照)

ここからが本編になります。
nが奇数のときはほとんどの確率でさっきの(x,y)が牛いるので、まわりを調べます。距離的にもあれだし牛は10000しかいないので100ちょっと×100ちょっとしらべれば最小値がみつかりそうです。余分に300くらいしらべてみました。マンハッタン距離の和とかは適当にlower_boundでもしてやって累積和をとればn^2になるのを回避できます。最小値を求めてそれに当てはまるものを数えます。

nが偶数のときは二つに分かれます。まずはさっきの場所(中央値2つのあいだならどこでもよい)の中に牛のいないスペースがある場合(適当に数えれば分かります)
このときは牛のいないスペースを引き算してもとめて出力すればよいです。
牛のいないスペースが無い場合は奇数のときと同じようにしてまわりを調べますが、このとき範囲はa/2-1-ほげとa/2+ほげの間になります。あとは奇数と同じです。

多分もっとちゃんとした解法があるかもしれませんが、こんなでも通ってしまうので許されると思います。要はN<=10000のおかげで助かっているイメージです。

source code

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> b[10000];
int x[10001];
int y[10001];
long long xx[10001];
long long yy[10001];
long long XX[10601];
long long YY[10601];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",x+i,y+i);
		b[i]=make_pair(x[i],y[i]);
	}
	std::sort(b,b+a);
	std::sort(x,x+a);
	std::sort(y,y+a);
	int now=0;
	for(int i=0;i<a;i++){
		xx[i+1]=now+=x[i];
	}
	now=0;
	for(int i=0;i<a;i++){
		yy[i+1]=now+=y[i];
	}
	if(a%2==1){
		int X=x[a/2];
		int Y=y[a/2];
		long long min=19999999999999LL;
		for(int i=X-300;i<=X+300;i++){
			int t=lower_bound(x,x+a,i)-x;
			XX[300+i-X]=xx[a]-xx[t]-(long long)(a-t)*i+t*i-xx[t];
		}
		for(int i=Y-300;i<=Y+300;i++){
			int t=lower_bound(y,y+a,i)-y;
			YY[300+i-Y]=yy[a]-yy[t]-(long long)(a-t)*i+t*i-yy[t];
		//	printf("%d %lld\n",i,YY[300+i-Y]);
		}
		for(int i=X-300;i<=X+300;i++){
			for(int j=Y-300;j<=Y+300;j++){
				if(!binary_search(b,b+a,make_pair(i,j))&&XX[i+300-X]+YY[j+300-Y]<min){
					min=XX[i+300-X]+YY[j+300-Y];
				}
			}
		}
		int count=0;
		for(int i=X-300;i<=X+300;i++){
			for(int j=Y-300;j<=Y+300;j++){
				if(!binary_search(b,b+a,make_pair(i,j))&&XX[i+300-X]+YY[j+300-Y]==min){
					count++;
				}
			}
		}
		printf("%lld %d\n",min,count);
	}else{
		int x1=x[a/2-1];
		int x2=x[a/2];
		int y1=y[a/2-1];
		int y2=y[a/2];
		int p=0;
		for(int i=0;i<a;i++)if(x1<=b[i].first&&b[i].first<=x2&&y1<=b[i].second&&b[i].second<=y2)p++;
		if(p==(x2-x1+1)*(y2-y1+1)){

			int X=x[a/2-1];
			int Y=y[a/2-1];
			long long min=19999999999999LL;
			for(int i=X-150;i<=x[a/2]+150;i++){
				int t=lower_bound(x,x+a,i)-x;
				XX[150+i-X]=xx[a]-xx[t]-(long long)(a-t)*i+t*i-xx[t];
			}
			for(int i=Y-150;i<=y[a/2]+150;i++){
				int t=lower_bound(y,y+a,i)-y;
				YY[150+i-Y]=yy[a]-yy[t]-(long long)(a-t)*i+t*i-yy[t];
			}
			for(int i=X-150;i<=x[a/2]+150;i++){
				for(int j=Y-150;j<=y[a/2]+150;j++){
					if(!binary_search(b,b+a,make_pair(i,j))&&XX[i+150-X]+YY[j+150-Y]<min){
						min=XX[i+150-X]+YY[j+150-Y];
					}
				}
			}
			int count=0;
			for(int i=X-150;i<=x[a/2]+150;i++){
				for(int j=Y-150;j<=y[a/2]+150;j++){
					if(!binary_search(b,b+a,make_pair(i,j))&&XX[i+150-X]+YY[j+150-Y]==min){
						count++;
					}
				}
			}
			printf("%lld %d\n",min,count);
		}else printf("%lld %d\n",xx[a]-xx[a/2]-(long long)(a-a/2)*x[a/2]+(a/2)*x[a/2]-xx[a/2]+yy[a]-yy[a/2]-(long long)(a-a/2)*y[a/2]+(a/2)*y[a/2]-yy[a/2],(x2-x1+1)*(y2-y1+1)-p);
	}
}