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パターンある。
三角形4つ切り落とさなきゃいけないのと、
台形2つ切り落とさなきゃいけないパターン。
どの角度で回転させた時、その境目となるのか?
それはこんな感じで
対角線を共有するように重ね合わせた時である。
この赤い三角形2つ
は、合同なので、回転角度の部分を半分に分けた感じ(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; }