AtCoder ABC #168 : F - . (Single Dot)

考察は余りなくて、実装が手間取る問題。
https://atcoder.jp/contests/abc168/tasks/abc168_f

問題

N本の縦線・M本の横線が与えられる。
これらの線で区切られた領域のうち、原点を含む領域の面積を求めよ。

解法

登場するX座標・Y座標はO(N+M)通り程度しかないので、まず座標圧縮しよう。
これらの座標で区切られた2次元グリッドにおいて、原点を含む面積を求めよう。

まず縦線横線それぞれ、累積和を使い縦横それぞれ隣接セル同士が線で区切られるかどうか判定する。
あとは連結する場所をUnion-Findで求めれば、原点と連結するセルの面積の総和を求めておしまい。
あらかじめ登場する座標の外側も圧縮対象に含めておくと、外周部のセルと連結するなら無限大とみなせてラク。

int N,M;
int X1[1010],X2[1010],Y[1010];
int X[1010],Y1[1010],Y2[1010];

int HNG[4040][4040];
int VNG[4040][4040];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<4000*4000> uf;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> Xs,Ys;
	Xs.push_back(-1<<30);
	Xs.push_back(0);
	Xs.push_back(1<<30);
	Ys.push_back(-1<<30);
	Ys.push_back(0);
	Ys.push_back(1<<30);
	FOR(i,N) {
		cin>>Y1[i]>>Y2[i]>>X[i];
		Xs.push_back(X[i]);
		Ys.push_back(Y1[i]);
		Ys.push_back(Y2[i]);
	}
	FOR(i,M) {
		cin>>Y[i]>>X1[i]>>X2[i];
		Xs.push_back(X1[i]);
		Xs.push_back(X2[i]);
		Ys.push_back(Y[i]);
	}
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	FOR(i,N) {
		X[i]=lower_bound(ALL(Xs),X[i])-Xs.begin();
		Y1[i]=lower_bound(ALL(Ys),Y1[i])-Ys.begin();
		Y2[i]=lower_bound(ALL(Ys),Y2[i])-Ys.begin();
		VNG[Y1[i]][X[i]]++;
		VNG[Y2[i]][X[i]]--;
	}
	FOR(i,M) {
		X1[i]=lower_bound(ALL(Xs),X1[i])-Xs.begin();
		X2[i]=lower_bound(ALL(Xs),X2[i])-Xs.begin();
		Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin();
		HNG[Y[i]][X1[i]]++;
		HNG[Y[i]][X2[i]]--;
	}
	
	
	FOR(x,Xs.size()) FOR(y,Ys.size()) {
		if(x) HNG[y][x]+=HNG[y][x-1];
		if(y) VNG[y][x]+=VNG[y-1][x];
		if(x&&VNG[y][x]==0) uf(y*4000+x,y*4000+x-1);
		if(y&&HNG[y][x]==0) uf(y*4000+x,(y-1)*4000+x);
	}
	
	
	int rx,ry;
	rx=lower_bound(ALL(Xs),0)-Xs.begin();
	ry=lower_bound(ALL(Ys),0)-Ys.begin();
	if(uf[ry*4000+rx]==uf[0]) return _P("INF\n");
	
	ll ret=0;
	FOR(x,Xs.size()-1) FOR(y,Ys.size()-1) if(uf[ry*4000+rx]==uf[y*4000+x]) {
		ret+=1LL*(Ys[y+1]-Ys[y])*(Xs[x+1]-Xs[x]);
	}
	cout<<ret<<endl;
	
	
		
}

まとめ

入力はグリッドでなく座標なのに、X座標が縦だったので最初混乱した。