TopCoderOpen 2019 Round4 : Medium InsidePoints

これは通ってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15643&rd=17659

問題

２次元座標中で(1,1)-(50,50)の範囲でN個の格子点の座標が指定される。
以下を満たす多角形を1つ構築せよ。

• 頂点数は300以下で、(-100,-100)-(100,100)の範囲に収まる。
• 各頂点は格子点にある。
• シンプルな多角形であり、辺同士が交差したりしない。
• この多角形に完全に含まれる格子点は、ちょうど入力の格子点のみである。

解法

まず(0,0)-(51,0)-(51,51)-(0,51)を結んだ矩形を考える。
この状態だと(1,1)-(50,50)がすべて含まれてしまうので、指定された以外の頂点を辺に載せてしまおう。
Y座標の大きい順考える。
今(0,Y+1)に端点があるとき、(*,Y)をどうするか考えよう。
(1,Y)～(50,Y)のうち、入力の点がない区間(L,Y)-(R,Y)を考える。L==Rでもよい。
そしたら(0,Y+1)-(R,Y)-(L,Y)-(-1,Y+1)と結ぼう。
区間が複数ありもっと左側に(L',Y)-(R',Y)があるなら続けて(-1,Y+1)-(R',Y)-(L',Y)-(-2,Y+1)と結ぼう。

class InsidePoints {
	public:
	vector<int> R;
	void add(int x,int y) {
		if(R.size() && R[R.size()-2]==x &&R[R.size()-1]==y) return;
		R.push_back(x);
		R.push_back(y);
	}
	vector <int> construct(vector <int> X, vector <int> Y) {
		vector<int> V[51];
		int i,x,y;
		R.clear();
		
		FOR(i,X.size()) V[Y[i]].push_back(X[i]);
		add(51,0);
		add(51,51);
		add(0,51);
		
		for(y=50;y>=1;y--) {
			int pre=51;
			sort(ALL(V[y]));
			reverse(ALL(V[y]));
			int x=0;
			FORR(xx,V[y]) {
				if(xx+2<=pre) {
					add(pre-1,y);
					add(xx+1,y);
					x--;
					add(x,y+1);
				}
				pre=xx;
			}
			add(pre-1,y);
			add(0,y);
		}
		
		return R;
	}
}

まとめ

EasyがChallengeで落とされたので、これ通ってよかった。