ARC029 B - 高橋君と禁断の書

問題概要

縦A × 横Bのノートがある。
箱がN個あり、各箱の大きさは縦C × 横Dである。
それぞれの箱にノートが入るかどうかを判定し、入る場合は"YES"を入らない場合は"NO"を出力せよ。
ただし、ノートを回転させたり平行移動させてもよい。

制約

• 1 ≤ A , B , C_i , D_i ≤ 300000
• 1 ≤ N ≤ 5000

解法

二分探索。
まずBよりもAの方が大きければswapする。
判定は、

• A ≤ C かつ B ≤ D
• A ≤ D かつ B ≤ C

を満たせば"YES"(これを満たす場合はノートは回転なしで入る。)

満たさなければ、角度で二分探索する。
そしてノートを回転させた結果(回転公式を使う)と箱の大きさを比較して箱に入れば"YES"。

以上を満たさなければ"NO"。

感想

まさかB問題で幾何よりの数学が出るとは思わなかった。
回転っていう考えは出ていたが実装がわからなかったので他の解法を考えていた。

コード

#include <bits/stdc++.h>

using namespace std;

double A,B;
bool check(double C,double D){
  if(A <= C && B <= D) return true;
  double l = 0, r = M_PI/2;
  for(int i = 0 ; i < 150 ; i++){
    double mid = (l + r) / 2;
    double h = A*cos(mid) + B*sin(mid);
    double w = A*sin(mid) + B*cos(mid);
    if(h <= C && w <= D) return true;
    if(h < C){
      l = mid;
    }else{
      r = mid;
    }
  }
  return false;
}

int main(){
  double C,D;
  int N;
  cin >> A >> B >> N;
  if(A > B) swap(A,B);
  for(int i = 0 ; i < N ; i++){
    cin >> C >> D;
    if(check(C,D) || check(D,C)){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
  }
  return 0;
}