TopCoder SRM441 Div1Hard

問題

「長方形の紙を横に折って、縦に折って、長方形の部分をペンキで塗って、折ったのを戻す」ということを何回かやった。ペンキで塗ったところは、重なっている下の部分へもペンキが染み込む。最終的に、ペンキが塗られていない部分の面積を求めよ。

解法

横に折る回数が1回で、縦に折る回数が少ないので、ペンキが塗られる部分を長方形の形ですべて列挙できる。それらをまとめて、ペンキが塗られる部分の面積がわかる。
横方向の「イベント」の回数が少ないので、横方向に座標圧縮して、各部分で縦方向に見ていって塗られている部分の長さを求めればよい。この方法だと、結果O(K^2 * Σfold * log(K^2 * Σfold) )になるはず。これで十分通る。
ちなみに、長方形で覆われている部分の面積を、長方形の個数をNとしてO(N log N)で求めるアルゴリズムがあり、それを使うともう少し速くなるかもしれない。

コード

#include <vector>
#include <algorithm>

using namespace std;

struct rect
{
	int x1, y1, x2, y2;
	
	rect()
	{
		x1 = y1 = x2 = y2 = 0;
	}
	
	rect(int a, int b, int c, int d)
	{
		x1 = a; y1 = b; x2 = c; y2 = d;
	}
};

class PaperAndPaint
{
	int W, H;
	vector<rect> r;
	pair<int, int> act[200000]; int ap;
	
	void trim(rect& r)
	{
		r.x1 = max(r.x1, 0); r.x1 = min(r.x1, W);
		r.y1 = max(r.y1, 0); r.y1 = min(r.y1, H);
		r.x2 = max(r.x2, 0); r.x2 = min(r.x2, W);
		r.y2 = max(r.y2, 0); r.y2 = min(r.y2, H);
	}
	
	void print(rect& r){ printf("%d %d %d %d\n", r.x1, r.y1, r.x2, r.y2); }
	
	long long count(int lx, int rx)
	{
		ap = 0;
		for(int i=0;i<r.size();i++){
			rect t = r[i];
			if(t.x1 <= lx && rx <= t.x2){
				act[ap++] = make_pair(r[i].y1, 1);
				act[ap++] = make_pair(r[i].y2, -1);
			}
		}
		sort(act, act+ap);
		
		long long ret = 0; int con = 0;
		for(int i=0;i<ap;i++){
			if(con>0){
				ret += act[i].first - act[i-1].first;
			}
			con += act[i].second;
		}
		
		printf("%d %d %lld\n", lx, rx, ret);
		return ret;
	}
	
public:
	long long computeArea(int width, int height, vector<int> xfold, vector<int> cnt, vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2)
	{
		rect tmp;
		
		W = width;
		H = height;
		for(int i=0;i<cnt.size();i++){
			int cv = cnt[i]+1, hv = height / cv;
			for(int j=0;j<cv;j++){
				if(j%2==0){
					tmp = rect(xfold[i] + x1[i], hv*j+y1[i], xfold[i] + x2[i], hv*j+y2[i]); trim(tmp); r.push_back(tmp);
					tmp = rect(xfold[i] - x2[i], hv*j+y1[i], xfold[i] - x1[i], hv*j+y2[i]); trim(tmp); r.push_back(tmp);
				}else{
					tmp = rect(xfold[i] + x1[i], hv*(j+1)-y2[i], xfold[i] + x2[i], hv*(j+1)-y1[i]); trim(tmp); r.push_back(tmp);
					tmp = rect(xfold[i] - x2[i], hv*(j+1)-y2[i], xfold[i] - x1[i], hv*(j+1)-y1[i]); trim(tmp); r.push_back(tmp);
				}
			}
		}
		
		vector<int> xev;
		xev.push_back(0);
		xev.push_back(W);
		for(int i=0;i<r.size();i++){
			xev.push_back(r[i].x1);
			xev.push_back(r[i].x2);
		}
		
		sort(xev.begin(), xev.end());
		xev.erase(unique(xev.begin(), xev.end()), xev.end());
		
		long long ret = (long long)W*H;
		for(int i=1;i<xev.size();i++){
			ret -= (xev[i]-xev[i-1]) * (long long)count(xev[i-1], xev[i]);
		}
		
		return ret;
	}
};