SRM585 Div2 Hard "EnclosingTriangleColorful"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12694
訳
あなたにint m が与えられる。2次元上の、角が(0, 0), (m, 0), (m, m), そして (0, m)の四角形を考える。四角形の辺の上の格子上のポイントには、以下のように色がついている。
(1, 0), ..., (m-1, 0)は赤 (m, 1), ..., (m, m-1)は緑 (m-1, m), ..., (1, m)は青 (0, m-1), ..., (0, 1)は黄
他の格子上のポイントは、いくつか黒で塗られている。それぞれの黒の点は四角形の中にある。あなたは2つのint[] x, y が与えられる。これは、それぞれの黒の点の座標を表している。
あなたは以下のようにして三角形を描きたい。
1. 三角形の頂点は{赤・緑・青・黄}のポイントの3つの違う色を使う 2. 全ての黒い点を、三角形の中に内包するようにする
いくつ三角形が描けるかを返せ。
制約
2 <= m <= 300
1 <= 黒い点の数 <= 50
他人のソースコードをカンニング
どの色を使うかは4パターンある。
で、このパターン①にとりあえず着目する。
左の辺と下の辺を使う直線は、黒い点を内包する三角形を作るときに使えるのかどうかを考える。
全ての黒い点が、この直線より上にあればOKで、この直線より下に、黒い点が1つでもあれば、使えないことになる。
左の辺で使うポイントを(0, h)、下の辺で使うポイントを(w, 0)とすると、この直線はこの2点を通るので、連立方程式を解けば直線の式が出てくる。
この直線より下に点があるとだめなので、判定は以下のような感じになる。
こんな感じで3つの直線を三角形に使えるかどうか、判定してやればよい。
回転する
残りの3パターンは黒い点の座標を回転してやればよい。同じことを4回繰り返せば答えが出る。
ソースコード
bool okl[330][330], okr[330][330]; class EnclosingTriangleColorful { public: int solve( int m, int n, vector<int> x, vector<int> y ){ for( int i = 1; i <= m - 1; i++ ){ for( int j = 1; j <= m - 1; j++ ){ okl[i][j] = true; for( int k = 0; k < n; k++ ){ // 左と下の点を使った直線が使えるか? if( y[k] * i < j * i - j * x[k] ){ okl[i][j] = false; break; } } okr[i][j] = true; for( int k = 0; k < n; k++ ){ // 右と下の点を使った直線が使えるか? if( y[k] * (m - i) < j * x[k] - j * i ){ okr[i][j] = false; break; } } } } int res = 0; for( int l = 1; l <= m - 1; l++ ){ for( int r = 1; r <= m - 1; r++ ){ bool ok = true; for( int k = 0; k < n; k++ ){ // 左と右の点を使った直線が使えるか? if( y[k] * m > (r - l) * x[k] + m * l ){ ok = false; break; } } if( !ok ) continue; // 使えるならば、その2点と下の点で三角形が作れるか? for( int i = 1; i <= m - 1; i++ ){ if( okl[i][l] && okr[i][r] ) res++; } } } return res; } int getNumber(int m, vector <int> x, vector <int> y){ int n = x.size(); // パターン1 int ans = solve( m, n, x, y ); // 回転して残りの3パターンをやる for( int i = 1; i < 4; i++ ){ for( int j = 0; j < n; j++ ){ int t = x[j]; x[j] = m - y[j]; y[j] = t; } ans += solve( m, n, x, y ); } return ans; } };