/* タイルを長方形PQRS, 荷物を長方形CDEFと呼ぶ。 長さはPQ=A, PS=B, CD=X, DE=Yである。 頂点Cを辺PS上、頂点Dを辺PQ上に置いたときに、 E,Fがタイルの中に収まるかどうかを判定。 CPの長さをtと置く。 0<=t<=X, 0<=t<=Bである。 このときDP=sqrt(X*X-t*t)となる。 Pを原点、PQをX軸、PSをY軸とする座標系をしくと、 E=(sqrt(X*X-t*t)+Y*t/X, y*sqrt(x*x-t*t)/X) F=(Y*t/X, t+y*sqrt(x*x-t*t)/X) となる。こいつらの座標がA,Bの中に収まる、という式を立てて 変形すると二次不等式になってそれを解く。 別解 by とし 収まる場合にはタイルと荷物の中心があった状態で収めることができる。 よって中心を合わせた状態で荷物を回転させると、 荷物の中心から各頂点までの距離は同じなので、 それら頂点の軌道を書けば解けそう。 */ #include #include #include #include #include using namespace std; typedef vector array; array quadricEquation(double a, double b, double c){ double D=b*b-4.0*a*c; if ( D<0.0 ) return array(); array res; // I'm sure a>0 && b<0 in this problem... double b_ = -b; res.push_back(2.0*c / (b_+sqrt(D))); // avoid cancellation res.push_back((b_ + sqrt(D)) / (2.0*a)); return res; } bool between(double a, double b, double c) { return a> ncases; while ( --ncases>=0 ) { double a,b,x,y; cin>> a>>b>>x>>y; array edges; edges.push_back(0.0); const double tmax = min(x,min(a*x/y,b)); edges.push_back(tmax); array range1(quadricEquation(x*x+y*y, -2*a*x*y, x*x*(a*a-x*x))); array range2(quadricEquation(x*x+y*y, -2*b*x*x, x*x*(b*b-y*y))); copy(range1.begin(), range1.end(), back_inserter(edges)); copy(range2.begin(), range2.end(), back_inserter(edges)); sort(edges.begin(), edges.end()); bool escaped=false; for ( int i=1 ; i