WARush

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

Codeforces #172 Div2 C "Rectangle Puzzle"

問題

W * Hの長方形の中心をA度反時計回りに回転させる。
元の長方形と、回転後の長方形の重なっている部分の面積を返せ。

制約

1 <= W, H <= 10^6
0 <= A <= 180

ACしているコードをカンニング
  • 基本的な考察

中心でぐるりと回すので、答えとなる面積は
面積(30度) == 面積(150度)
面積(60度) == 面積(120度)
面積(80度) == 面積(100度)
と90度を中心に対称的になるから
角度0~90までを考えればよい。

角度が90度の時は簡単に面積は分かる。
面積はWとHの小さいほうを一辺とした正方形となる。

  • 問題のキモ

角度によって求め方が2パターンある。

f:id:Ekaing:20130312202410j:plain
三角形4つ切り落とさなきゃいけないのと、

f:id:Ekaing:20130312202437j:plain
台形2つ切り落とさなきゃいけないパターン。

どの角度で回転させた時、その境目となるのか?
それはこんな感じで
f:id:Ekaing:20130312202844j:plain
対角線を共有するように重ね合わせた時である。

この赤い三角形2つ
f:id:Ekaing:20130312202956j:plain
は、合同なので、回転角度の部分を半分に分けた感じ(A / 2)になる。
この三角形はWとHを辺にしてるので、W * tan(A/2) = Hとなる。

ここからさらに回すと台形2つのパターンになるし、 (W * tan(A/2) >= H)
これより回さない場合は三角形4つのパターンになる。(W * tan(A/2) < H)

後は、補助線書いて合同の三角形を見つければ、
三角関数を使って切り落とすべき面積が分かる。

ソースコード
int main() {
    double W, H, deg;
    cin >> W >> H >> deg;
    
    if( W < H ){
        swap( W, H );
    }

    if( deg == 90 ){
        printf( "%lf\n", H*H );
        return 0;
    }

    if( deg > 90 ){
        deg = 180 - deg;
    }

    double r = deg * M_PI / 180.0;

    double ans;
    if( W * tan(r/2) >= H ){ // 台形2個切り落としパターン
        double top = W / 2 - (H / 2 * tan(r/2));
        double bot = top - (H / tan(r));
        ans = W * H - ((top + bot) * H); 
    }else{                     // 三角形4個切り落としパターン
        double t1w = W / 2 - (H / 2 * tan(r/2));
        double t1h = t1w * tan(r);
        double t2w = H / 2 - (W / 2 * tan(r/2));
        double t2h = t2w * tan(r);
        ans = W * H - t1w * t1h - t2w * t2h;
    }
    printf( "%lf\n", ans );
    return 0;
}