POJ-3168 : Barn Expansion

問題概要

N(<25000)個の軸に平行な長方形がある。これらは端点以外では交わっていない。このとき、他のどの長方形とも共有点を持たないものがいくつあるか判定する問題。

解法

平面走査でやるのはすぐに見えるけど、簡潔な実装方法を選べないと厳しい。Range Sum Queryで区間に足し込み、新たに線分を加えるときオーバーラップしているかどうか判定する方法でやった。走査線を左右、上下の4方向に動かせば全部検出できる。
TLEがかなりきつい。

acceptされたコード

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 25000;
const int INF = int(1.05e9); 

RangeSumQuery eventline;

int N;
int xs[MAX_N][2], ys[MAX_N][2];
int numX[2*MAX_N], numY[2*MAX_N];
bool removed[MAX_N];
int X, Y;
pair< pair<int,int>, pair<int,int> > add[MAX_N], rem[MAX_N];//(x,id), (y0,y1)

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d%d%d", xs[i]+0, ys[i]+0, xs[i]+1, ys[i]+1);
	}
}

void subSolve() {
	for (int i = 0; i < N; ++i) {
		add[i] = make_pair(make_pair(xs[i][0], i), make_pair(ys[i][0], ys[i][1]));
		rem[i] = make_pair(make_pair(xs[i][1], i), make_pair(ys[i][0], ys[i][1]));
	}
	sort(add, add + N);
	sort(rem, rem + N);

	eventline.init(Y+1);
	for (int a = 0, r = 0; a < N && r < N;) {
		
		for (;a < N && add[a].first.first <= rem[r].first.first; ++a) {
			const int y0 = add[a].second.first,
					y1 = add[a].second.second;
			if (eventline.getSum(y0, y1+1) > 0) {
				const int id = add[a].first.second;
				removed[id] = true;
			}
			eventline.add(y0, y1+1, 1);
		}

		
		for (;r < N && (a == N || rem[r].first.first < add[a].first.first); ++r) {
			const int y0 = rem[r].second.first,
					y1 = rem[r].second.second;
			eventline.add(y0, y1+1, -1);
		}
	}
}

int solve() {
	for (int i = 0; i < N; ++i) {
		for (int k = 0; k < 2; ++k) {
			numX[2*i+k] = xs[i][k];
			numY[2*i+k] = ys[i][k];
		}
	}
	sort(numX, numX + 2*N);
	X = unique(numX, numX + 2*N) - numX;
	sort(numY, numY + 2*N);
	Y = unique(numY, numY + 2*N) - numY;
	for (int i = 0; i < N; ++i) {
		for (int k = 0; k < 2; ++k) {
			xs[i][k] = lower_bound(numX, numX + X, xs[i][k]) - numX;
			ys[i][k] = lower_bound(numY, numY + Y, ys[i][k]) - numY;
		}
	}
	for (int _ = 0; _ < 2; ++_) {
		for (int __ = 0; __ < 2; ++__) {
			subSolve();
			for (int i = 0; i < N; ++i) {
				for (int k = 0; k < 2; ++k) {
					xs[i][k] = X - 1 - xs[i][k];
				}
				swap(xs[i][0], xs[i][1]);
			}
		}
		for (int i = 0; i < N; ++i) {
			for (int k = 0; k < 2; ++k) {
				swap(ys[i][k], xs[i][k]);
			}
		}
		swap(X, Y);
	}

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		if (!removed[i]) {
			++ans;
		}
	}
	return ans;
}


int main() {
	init();
	printf("%d\n", solve());
	return 0;
}