なんかレートが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割ぐらいかな。