POJ-1693: Counting Rectangles

keyword

平面走査法　座標圧縮　C++

問題概要

X軸に平行あるいは垂直な線分がS(<100)本与えられる。存在する長方形の数を数え上げる問題。

解法

まず座標圧縮する。その後は平面走査法でx座標の小さい方から舐めていく。計算量O(S^3)。

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

struct segment{
	int x1, y1, x2, y2;
};

int S;
int X, Y;
segment segs[109];

int solve(){
	vector< vector< vector<bool> > > segx(X, vector< vector<bool> >(Y, vector<bool>(Y, false))), segy(Y, vector< vector<bool> >(X, vector<bool>(X, false)));

	for(int i=0; i<S; i++){
		if(segs[i].x1 == segs[i].x2){
			int miny = min(segs[i].y1, segs[i].y2);
			int maxy = max(segs[i].y1, segs[i].y2);
			for(int j=miny; j < maxy; j++){
				for(int k=j+1; k<=maxy; k++){
					segx[segs[i].x1][j][k] = true;
				}
			}
		}
		else if(segs[i].y1 == segs[i].y2){
			int minx = min(segs[i].x1, segs[i].x2);
			int maxx = max(segs[i].x1, segs[i].x2);
			for(int j=minx; j < maxx; j++){
				for(int k=j+1; k<=maxx; k++){
					segy[segs[i].y1][j][k] = true;
				}
			}
		}
	}

	int ans = 0;
	vector< vector<int> > dp(Y, vector<int>(Y,0));
	for(int k=0; k<X; k++){
		for(int i=0; i<Y; i++){
			for(int j=i+1; j<Y; j++){
				if(k==0 || (segy[i][k-1][k] && segy[j][k-1][k])){
					if(segx[k][i][j]){
						ans += dp[i][j];
						dp[i][j]++;
					}
				}
				else {
					dp[i][j] = segx[k][i][j]?1:0;
				}
			}
		}
	}

	return ans;
}

int main(){
	int M;
	scanf("%d", &M);
	for(int i=0; i<M; i++){
		scanf("%d",&S);
		vector<int> xs, ys;
		for(int j=0; j<S; j++){
			int x1, x2, y1, y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			segs[j] = (segment){x1,y1,x2,y2};
			xs.push_back(x1); xs.push_back(x2);
			ys.push_back(y1); ys.push_back(y2);
		}
		sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
		sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
		X = xs.size(); Y = ys.size();
		for(int j=0; j<S; j++){
			segs[j].x1 = distance(xs.begin(), lower_bound(xs.begin(), xs.end(), segs[j].x1));
			segs[j].x2 = distance(xs.begin(), lower_bound(xs.begin(), xs.end(), segs[j].x2));
			segs[j].y1 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), segs[j].y1));
			segs[j].y2 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), segs[j].y2));
		}
		printf("%d\n",solve());
	}
	return 0;
}