AIM Tech Round : C. Electric Charges

Dより難しかったっぽいC。
http://codeforces.com/contest/623/problem/C

問題

2次元座標においてN個の頂点が与えられる。
各頂点についてX,Y座標どちらかを0にしたとき、全頂点を含む円の直径を最小化し、その二乗を求めよ。

解法

Editorialを見て回答。

全頂点に対しX座標を0にした場合、及びY座標を0にした場合は容易に計算できる。
それ以外の場合を二分探索で絞り込む。

Y座標を0にした頂点群について、最小のX座標をXl、最大のX座標をXrとする。
X座標を0とした頂点群との距離を考えるときは、|Xl|と|Xr|のうち大きい方だけを考えればよい。

そこで、まず全頂点をX座標でソートしその後X[i]＜0がXlになるケースを考える。
直径を√M以下にしたいので、Xr=min(|Xl|,Xl + √M)とするとXl ≦ x ≦ Xrとなる頂点群はY座標を0にした方が良い。
そのような頂点群の範囲は尺取法やlower_boundで高速に求めることができる。

逆に、x＜Xlまたはmin(|Xl|,Xl + √M)＜xとなる頂点はX座標を0にするしかない。
これらのX座標を0にした頂点群に対し、事前に前処理をしておくとY座標の最大値Yt・最小値Ybを容易に求めることが出来る。
すると、各頂点は4点(Xl,0)(Xr,0)(0,Yt)(0,Yb)で囲まれた範囲に含まれるので、この４点間の距離が√M以下であることを計算すればよい。

上記処理ではY座標を0にしたもっとも左の頂点X[i]を総当たりしたが、同様に最も右の頂点を総当たりするケースも行う。

int N;
ll X[101010],Y[101010];
pair<ll,ll> P[101010];
ll Lmiy[101010],Lmay[101010];
ll Rmiy[101010],Rmay[101010];

int ok(ll v) {
	int L,R;
	
	R=0;
	FOR(L,N) {
		if(X[L]>0) break;
		ll ri=min(-X[L],X[L]+(ll)sqrt(v+1e-8));
		while(R+1<N && X[R+1] <= ri) R++;
		while(X[R] > ri) R--;
		
		ll miy=min(Rmiy[R+1],Lmiy[L]);
		ll may=max(Rmay[R+1],Lmay[L]);
		ll ma=max(may,-miy);
		if(max((may-miy)*(may-miy),X[L]*X[L]+ma*ma)<=v) return 1;
		
	}
	L=N-1;
	for(R=N-1;R>=0;R--) {
		if(X[R]<0) break;
		ll le=max(-X[R],X[R]-(ll)sqrt(v+1e-8));
		while(L>0 && X[L-1] >= le ) L--;
		while(X[L] < le) L++;
		
		ll miy=min(Rmiy[R+1],Lmiy[L]);
		ll may=max(Rmay[R+1],Lmay[L]);
		ll ma=max(may,-miy);
		if(max((may-miy)*(may-miy),X[R]*X[R]+ma*ma)<=v) return 1;
	}
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	FOR(i,N) X[i]=P[i].first,Y[i]=P[i].second;
	
	FOR(i,N) {
		Lmay[i+1]=max(Lmay[i],Y[i]);
		Lmiy[i+1]=min(Lmiy[i],Y[i]);
	}
	for(i=N-1;i>=0;i--) {
		Rmay[i]=max(Rmay[i+1],Y[i]);
		Rmiy[i]=min(Rmiy[i+1],Y[i]);
	}
	
	ll ret=(1LL<<60)-1;
	for(i=59;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
	ll mixx=*min_element(X,X+N);
	ll maxx=*max_element(X,X+N);
	ll miyy=*min_element(Y,Y+N);
	ll mayy=*max_element(Y,Y+N);
	ret=min(ret,(maxx-mixx)*(maxx-mixx));
	ret=min(ret,(mayy-miyy)*(mayy-miyy));
	
	cout<<ret<<endl;
	
}

まとめ

パッと見そんなに難しくなさそうと思ったら、X,Yが非負だと勘違いしていた…。