SRM 203 DIV1 Hard TurfRoller
問題
長方形Aが一つ与えられる。
別の長方形Bが与えられ、それを幾つか置いて先の長方形Aを被覆したい。
ただし、置くのに、与えられた角度だけ回転させて置かなければならない。
置く長方形の数を最小化せよ。
- -100<=全ての座標, 大きさ<=100
- 0<=角度<=90
- 角度が0と90以外なら、もし長さが0.1未満変わったとしても答えは同じになる(誤差を許容)
解答
長方形Aを最初に、長方形Bの角度分、逆に回転させておく。
置き方として、先に上に置いたものと接していない置き方では最小数では絶対被覆できず(隙間ができる)、横に複数置くときもぴったり合っていないといけない。
そのため単に、レンガのように、縦に対して段になっていて、段ごとに横の数がある、という感じにできる。
ここで、段ごとに横の数を考えなければいけない。
これは、そのy位置の範囲に対しての、長方形の外周の線分の最小と最大のx座標を求め、ceil((最大x-最小x)/B幅)でできる。
線分の最小と最大の座標だが、これは適当にやったらできた。
あとは最初に置くy位置を全探索した
コメント
いちおう書けたのはいいね。
でもSRMではかなり限られた時間で書けないと駄目なんだよね。2時間弱かかってるし。
今は時間気にせず頑張って書き上げることかな。楽しいし
コード
#include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <complex> #include <limits> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define pb(x) push_back(x) #define INF 0x3f3f3f3f #define EPS 1e-9 using namespace std; #define double long double typedef complex<double> P; struct TurfRoller { P rotate(P x, double s) { const double pi = acos(-1.); //オイラーの公式すら覚えていないという数学ひどさ return x * P(cos(s*pi), sin(s*pi)); } double calcx(P p, P q, double y) { //普通に直線の式を解く double x0 = real(p), x1 = real(q), y0 = imag(p), y1 = imag(q); if(abs(x0 - x1) < EPS) return x0; double a = (y0 - y1) / (x0 - x1), b = (x0*y1 - x1*y0) / (x0 - x1); return (y - b) / a; } bool LE(double x, double y) { return x <= y + EPS; } int stripNum(int lawnWidth, int lawnHeight, int stripAngle, int stripLength, int stripBreadth) { const double inf = numeric_limits<double>::infinity(); double r = stripAngle / 180.; P l[4] = {P(0, 0), rotate(P(lawnWidth, 0), r), rotate(P(lawnWidth, lawnHeight), r), rotate(P(0, lawnHeight), r)}; int mincount = INF; //誤差0.1なのでなんとなく0.05単位でやった for(double yfirst = 0; yfirst > -stripBreadth; yfirst -= 0.05) { double y = yfirst; int count = 0; while(1) { double y0 = y, y1 = y + stripBreadth; double xmin = inf, xmax = -inf; //[y0,y1]に含まれている点のなかでのx座標の最大,最小を求める rep(i, 4) { P p = l[i], q = l[(i+1)%4]; if(imag(p) > imag(q)) swap(p, q); vector<double> v; if(abs(imag(p) - imag(q)) < EPS) { //ここ適当 if(LE(y0, imag(p)) && LE(imag(p), y1)) v.pb(inf), v.pb(-inf); if(LE(y0, imag(q)) && LE(imag(q), y1)) v.pb(inf), v.pb(-inf); if(LE(imag(p), y0) && LE(y0, imag(q))) v.pb(inf), v.pb(-inf); if(LE(imag(p), y1) && LE(y1, imag(q))) v.pb(inf), v.pb(-inf); }else { //4パターンの最大最小を考えた。線分の始点・終点と、ちょうど範囲ぎりぎりの所 if(LE(y0, imag(p)) && LE(imag(p), y1)) v.pb(calcx(p, q, imag(p))); if(LE(y0, imag(q)) && LE(imag(q), y1)) v.pb(calcx(p, q, imag(q))); if(LE(imag(p), y0) && LE(y0, imag(q))) v.pb(calcx(p, q, y0)); if(LE(imag(p), y1) && LE(y1, imag(q))) v.pb(calcx(p, q, y1)); } each(x, v) { //直線でなく線分なので、範囲で切り落とす。適当 *x = max(*x, min(real(p), real(q))); *x = min(*x, max(real(p), real(q))); xmin = min(xmin, *x); xmax = max(xmax, *x); } } if(xmin == inf) break; //ひとつの点も無いってことは当たっていなくて、それ以降に当たることも無い count += ceil((xmax - xmin) / stripLength - EPS); //yはできる限り大きくなったほうがいいので、適当にEPSした //今思えば角度0,90だけ誤差が別な問題なのでそれを場合分けすればよかったか y += stripBreadth + EPS; } mincount = min(count, mincount); } return mincount; } }; #undef double
