Codeforces #220 Div2. E. Inna and Babies

一見面倒だけどなかなか面白い。
Editorialはまだ出てないけど、周囲の解答や解説を参考に解いた。
http://codeforces.com/contest/374/problem/E

問題

２次元座標上にN個の青い点とM個の赤い点が与えられる。
時間T後、各点の元の座標(x,y)に対し、青い点は(x-t,y+t)-(x+t,y-t)、赤い点は(x-t,y-t)-(x+t,y+t)からなる線分となる。

時間経過とともに、周囲を線で囲まれた面積が正である四角形ができるか。
できるなら最短時間を求めよ。

解法

青い点と赤い点は斜めの線分となるが、面倒なのでX=x+y、Y=x-yで座標変換するとよい。
青い点はY軸方向、赤い点はX軸方向に時間当たり2ずつ伸びることになる。

まず最初に四角形の有無を考える。
無限に時間が経っても四角形ができないのは、青い点の(座標変換後の)X座標が1通りしかないか赤い点の(座標変換後の)Y座標が1通りしかない場合である。
逆に、いずれも２通り以上あれば時間経過によりいずれ四角形ができる。

次に、時間tを二分探索で求めていく。
まず時間t後の線分を列挙する。複数の線分が重なる場合があるが、それらは合わせて１つの長い線分と考える。
後は青い線分と赤い線分が四角形を成すか判定すればよい。
愚直に行うと回ループを回すのでTLEするが、「ある２つの青い線分が共に１つの赤い線分と交わる」といった赤い線分を２つ探すと考えると、おおむねO(NM)で処理を完了することができる。

int N,M;
int BX[2010],BY[2010];
int RX[2010],RY[2010];
map<int,vector<int> > R,B;

void generate(map<int,vector<int> >& LS, vector<pair<int,pair<int,int> > >& VV,double le) {
	int i,j,x,ny1,ny2;
	
	VV.clear();
	ITR(it,LS) {
		x=it->first;
		ITR(it2,it->second) {
			ny1 = *it2 - 2*le;
			ny2 = *it2 + 2*le;
			
			bool conn = !VV.empty();
			if(!VV.empty()) {
				if(VV.back().first != x) conn=false;
				if(VV.back().second.second < ny1) conn=false;
			}
			if(conn) VV.back().second.second = ny2;
			else VV.push_back(make_pair(x,make_pair(ny1,ny2)));
		}
	}
}

int okok(int le) {
	int i,j,r,b;
	static int vis[2001][2001];
	vector<pair<int,pair<int,int> > > BV,RV;
	generate(B,BV,le);
	generate(R,RV,le);
	
	ZERO(vis);
	FOR(b,BV.size()) {
		vector<int> rr;
		FOR(r,RV.size()) {
			if(BV[b].first < RV[r].second.first || BV[b].first > RV[r].second.second) continue;
			if(RV[r].first < BV[b].second.first || RV[r].first > BV[b].second.second) continue;
			ITR(itr,rr) if(++vis[*itr][r]>=2) return 1;
			rr.push_back(r);
		}
	}
	
	return 0;
}


void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		B[x+y].push_back(x-y);
	}
	FOR(i,M) {
		cin>>x>>y;
		R[x-y].push_back(x+y);
	}
	
	if(B.size()<2 || R.size()<2) return _P("Poor Sereja!\n");
	ITR(it,B) sort(it->second.begin(),it->second.end());
	ITR(it,R) sort(it->second.begin(),it->second.end());
	
	int ll=0,rr=1<<25,p;
	FOR(i,60) {
		p=(ll+rr)/2;
		if(okok(p)) rr=p;
		else ll=p;
	}
	_P("%d\n",rr);
}

まとめ

他人の解法を見て知ったけど、この四角形判定の高速化はためになるな。
最初回ループを回すのかと頭を抱えちゃったよ。