SRM 270 DIV1 Hard PackingShapes

問題 Editorial

問題

(問題の肝の部分のみ)
width*heightの長方形の中にx*yの長方形が回転してでも入るかどうかを判定せよ

• 全ての数値は整数, [1,1000]

解答

回転後の幅と高さは(x cosθ + y sinθ, x sinθ + y cosθ)。
それを適当にいろんな感じで二分探索しまくったら通った。
厳密な代数的解はEditorial参照

コメント

こういう適当に二分探索しまくるというのは結構使える。
しかしEditorialの解がわかってない。こういう式の解くのは苦手としてるな。普通に算数として練習するべきか

コード

#include <string>
#include <vector>
#include <sstream>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define pb(x) push_back(x)
using namespace std;
typedef vector<string> vs; typedef long double ld;
struct PackingShapes {
	bool check(int w, int h, int x, int y, int t, bool b) {
		const ld pi = acos(-1.L);
		ld l = pi / 4. * t, u = pi / 4. * (t+1);
		rep(ii, 200) {
			ld m = (l+u) / 2;
			((x*abs(cos(m))+y*abs(sin(m)) <= w) == b ? u : l) = m;
		}
		return x*abs(cos(u))+y*abs(sin(u)) <= w+1e-9L && x*abs(sin(u))+y*abs(cos(u)) <= h+1e-9L;
	}
	vector <string> tryToFit(int w, int h, vector <string> shapes) {
		vs r;
		rep(i, shapes.size()) {
			bool ok = false;
			stringstream ss(shapes[i]);
			string type;
			ss >> type;
			if(type == "CIRCLE") {
				int x;
				ss >> x; x *= 2;
				ok = x <= w && x <= h;
			}else {
				int x, y;
				ss >> x >> y;
				rep(wh, 2) {
					rep(xy, 2) {
						rep(j, 8) rep(b, 2) ok |= check(w, h, x, y, j, b);
						swap(x, y);
					}
					swap(w, h);
				}
			}
			r.pb(ok ? "YES" : "NO");
		}
		return r;
	}
};