Rockethon 2014 : D2. Supercollider

通ったけどちょっと納得行ってない問題。
http://codeforces.com/contest/391/problem/D2

問題

２次元座標上で、X軸またはY軸に平行な線分がそれぞれN本・M本ある。
これらの線分群の一部から得られる中心から終端までの長さが均一な十字のうち、長さが最長のものを答えよ。

解法

総当たりだとO(NM)で交差判定をして解けるが、N<=50000、M<=50000だとTLEする。
そこで縦線および横線をそれぞれ始点のX座標順にソートする。

各横線に対し縦線をX座標順に交差判定するが、これ以上続けても最大値を更新しないX座標に到達したらそれ以上の探索を打ち切る。
そうするとTLEしなくなる。

下記コードでテストは通ったが、テストケース次第ではTLEするケースが作れそうな気がする。
例えば縦線をX座標負の場所に大量に置き、横線をX座標が正の位置に置くと探索打ち切りができない。

int N,M;
struct hoge {int x,y,l;};
hoge V[50001],H[50001];

bool cmp(const hoge& l,const hoge& r) {
	return l.x<r.x;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>V[i].x>>V[i].y>>V[i].l;
	FOR(i,M) cin>>H[i].x>>H[i].y>>H[i].l;
	sort(V,V+N,cmp);
	sort(H,H+M,cmp);
	int ma=0;
	FOR(i,M) {
		FOR(j,N) {
			if(V[j].x-H[i].x<=ma) continue;
			if(H[i].x+H[i].l-V[j].x<=ma) continue;
			int miw = min(V[j].x-H[i].x,H[i].x+H[i].l-V[j].x);
			int mih = min(H[i].y-V[j].y,V[j].y+V[j].l-H[i].y);
			ma=max(ma,min(miw,mih));
		}
	}
	
	cout << ma << endl;
}

まとめ

Editorialがなぜかずっと見られず、想定解がわからない…。