kmjp's blog

競技プログラミング参加記です

TopCoder SRM 763: Div1 Easy CutCutCut

なんかレートがHighest更新した。
https://community.topcoder.com/stat?c=problem_statement&pm=15568&rd=17614

問題

2次元座標上で、(0,0)-(10000,10000)を対角線とする軸に平行な正方形がある。
ここを、Q個の直線で分割していくことを考える。
各直線と正方形の輪郭との交点が与えられるので、直線を1個追加するたび、正方形が何個に分割されるか答えよ。
なお、3本以上の直線が1点で交わることはなく、また直線同士の交点は辺上にあることはない。

解法

直線を追加すると、(1+(以前の直線との交点))数だけ分割数が追加されるので、交点数を毎回求めていこう。
符号付面積で判定してもよいし、辺との2交点が交互に現れるかどうかを判定してもよい。

class CutCutCut {
	public:
	vector <int> findPieces(vector <int> X1, vector <int> Y1, vector <int> X2, vector <int> Y2, int Q) {
		vector<int> V;
		
		map<pair<int,int>,int>  ID;
		
		int i,j;
		FOR(i,10000) ID[{i,0}]=i;
		FOR(i,10000) ID[{10000,i}]=i+10000;
		FOR(i,10000) ID[{10000-i,10000}]=i+20000;
		FOR(i,10000) ID[{0,10000-i}]=i+30000;
		
		int ret=1;
		FOR(j,Q) {
			ret++;
			FOR(i,j) {
				vector<pair<int,int>> A;
				A.push_back({ID[{X1[i],Y1[i]}],i});
				A.push_back({ID[{X2[i],Y2[i]}],i});
				A.push_back({ID[{X1[j],Y1[j]}],j});
				A.push_back({ID[{X2[j],Y2[j]}],j});
				sort(ALL(A));
				if(A[0].second==A[2].second) ret++;
			}
			V.push_back(ret);
		}
		return V;
		
		
	}
}

まとめ

こっちのアプローチ取る人少ないかと思ったら結構いた。
体感3割ぐらいかな。