WARush

SRMの結果とか、解けた問題のコードを書いていきます

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パターンある。
f:id:Ekaing:20130801001357j:plain

で、このパターン①にとりあえず着目する。
f:id:Ekaing:20130801001405j:plain


左の辺と下の辺を使う直線は、黒い点を内包する三角形を作るときに使えるのかどうかを考える。
f:id:Ekaing:20130801001424j:plain

全ての黒い点が、この直線より上にあればOKで、この直線より下に、黒い点が1つでもあれば、使えないことになる。
f:id:Ekaing:20130801001432j:plain

左の辺で使うポイントを(0, h)、下の辺で使うポイントを(w, 0)とすると、この直線はこの2点を通るので、連立方程式を解けば直線の式が出てくる。
f:id:Ekaing:20130801001715j:plain

この直線より下に点があるとだめなので、判定は以下のような感じになる。
f:id:Ekaing:20130801001721j:plain

こんな感じで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;
    }
};