WARush

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

SRM587 Div1 Medium "TriangleXor"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12528

整数Wが与えられる。XY座標上に四隅が(0, 0), (0, 1), (W, 0), (W, 1)の四角形がある。T[x]を(0, 1), (W, 1) そして (x, 0)を頂点とした三角形とする。

課題は、T[0] xor T[1] xor ... xor T[W]の面積を計算する事である。Wが1~6のときの計算すべき面積を図で示す。(問題のリンクを参照してください)

面積の、整数部部を返せ。

制約

1 <= W <= 70000



解法

こちらを参考にしました。m(_ _)m
Hiro180の日記 - SRMとかCFとかについて

このとおり、上下左右にわけて考える。
f:id:Ekaing:20130817205524j:plain

上(赤)の部分は簡単で、W % 2 == 0であるかどうかで、面積として加算するかしないか決めるだけ。

左右(黄・緑)の部分は、四角形の左下から右上に向かう対角線に対し、左上の頂点から垂線を垂らし、その長さを計算する(青色の線)。それから、面積として計算しなくてはならない三角形の、対角線上の線の長さの合計を計算する(赤色の線)。そうすると、求めるべき面積は、青色の線の長さ * 赤色の線の長さ / 2となる。それが左右にあるから / 2はいらない。
f:id:Ekaing:20130817211001j:plain

下(青)の部分は、下記の図のようにする
f:id:Ekaing:20130817211010j:plain

ほそく

この計算をするには2直線(y = ax + b, y = cx + d)の交点を出さなくてはならないが、これは連立方程式を解けば、以下のような公式を得られる。

x = (d - b) / (a - c)
y = (ad - bc) / (a - c)

ソースコード

double xs[70050]; // 交点のx座標
double ys[70050]; // 交点のy座標

class TriangleXor {
public:
    // 2点(x1, y1) (x2, y2)の距離を求める
    double len( double x1, double y1, double x2, double y2 ){
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }

    // y = ax + bとy = cx + dの交点の座標を求める
    void cross( double a, double b, double c, double d, double* x, double* y ){
        *x = (d - b) / (a - c);
        *y = ((a * d) - (b * c)) / (a - c);
    }

    int theArea(int W){

        // 交点を取得する
        xs[0] = ys[0] = 0;
        for( int i = 1; i <= W; i++ ){
            cross( 1.0 / W, 0, -1.0 / i, 1, &xs[i], &ys[i] );
        }

        double ans = 0; 

        // 上
        if( W % 2 == 0 ){
            ans += W / 4.0;
        }

        // 左右
        double x, y;
        cross( 1.0 / W, 0, -W, 1, &x, &y );
        double h = len( 0, 1, x, y ); // 青の線の長さ 
        double w = 0; // 赤の線の長さの合計
        for( int i = 0; i + 1 <= W; i += 2 ){
            w += len( xs[i], ys[i], xs[i+1], ys[i+1] );
        }
        ans += h * w;

        // 下
        for( int i = 1; i < W; i += 2 ){
            w = W - xs[i] * 2;
            ans += w * ( ys[i] - ys[i-1] ) / 2;
            ans += w * ( ys[i+1] - ys[i] ) / 2;
        }

        return (int)ans;
    }
};