Codeforces #187 Div1 D. Sereja and Straight Lines

これはDの割には簡単。
http://codeforces.com/contest/314/problem/D

問題

２次元座標上、N個の格子点の座標(X[i],y[i])が与えられる。

ここで、X軸と45度で交わり、互いに直角である２本の直線を引く。
この際、各格子点と２本いずれかの直線との距離の小さい方のうち、最大値を最小化せよ。
なお、点と直線の距離はユークリッド距離でなくマンハッタン距離で算出する。

解法

X軸と45度交わる、というのはわかりにくいので、X'=X+Y、Y'=X-Yで座標変換し、全体を45度傾ける。

求める答えをWとすると、縦に幅2Wの線を１本ひき、横に幅2Wの線を１本ひいたとき、全ての格子点をいずれかの線上に乗せられる最小のWを求めればよい。
Wは二分探索で求める。

まず格子点をX'[i]で昇順ソートしておく。
Wの縦線の左端を、あるX'[L]に合わせた場合、X'座標がX'[L]～X'[L]+2Wの範囲の格子点は縦線上に乗る。
縦線に乗る格子点の右端をX'[R]とすると、残された0～(L-1)番および(R+1)～(N-1)番の頂点が横線の上に乗ればWは条件を満たすことになる。

そのためには、事前にY'[0]～Y'[i]の最大値最小値と、Y'[j]～Y'[N-1]の最大値最小値を求めておけば、横線に乗るかどうかはO(1)で判定できる。

X[L]に対するRはlower_boundでも良いが尺取法で行った方が計算量が小さくて済む。
全体ではO(N*log(maxX))程度かな。

int N;
pair<ll,ll> P[100200];
ll miy[100200][2],may[100200][2];

int ok(ll w) {
	int x,y;
	
	y=0;
	FOR(x,N) {
		while(y<N && P[y].first <= P[x].first+w) y++;
		if(x==0 && y==N) return 1;
		if(x==0 && may[y][1]-miy[y][1]<=w) return 1;
		if(x>0 && y==N && may[x-1][0]-miy[x-1][0]<=w) return 1;
		if(x>0 && y<N && max(may[x-1][0],may[y][1])-min(miy[x-1][0],miy[y][1])<=w) return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		P[i].first=x+y;
		P[i].second=x-y;
	}
	sort(P,P+N);
	miy[0][0]=may[0][0]=P[0].second;
	for(i=1;i<N;i++) miy[i][0]=min(miy[i-1][0],P[i].second);
	for(i=1;i<N;i++) may[i][0]=max(may[i-1][0],P[i].second);
	miy[N-1][1]=may[N-1][1]=P[N-1].second;
	for(i=N-2;i>=0;i--) miy[i][1]=min(miy[i+1][1],P[i].second);
	for(i=N-2;i>=0;i--) may[i][1]=max(may[i+1][1],P[i].second);
	
	ll ret=0;
	if(ok(0)) return _P("0\n");
	for(i=32;i>=0;i--) if(ok(ret+(1LL<<i))==0) ret+=1LL<<i;
	_P("%lf\n",(ret+1)/2.0);
	
}

まとめ

これマンハッタン距離である必要あるのかな。