学步园

这个题哈。。之前和会升讨论过，推算公式无果，他用神马离散化过掉了。。。我今天重新看这题，也用了那个方法。。

传说中的离散化，这题感觉就是，一个一个试。。。

把里面的矩形每次旋转一定角度，然后根据角度求出包含它的最小矩形的长宽，然后和给的对比。

开始用弧度，死活过不去，后来看会升的，他居然判等了= =。。明明题目上说不能碰边界的。。。我改成等后zoj还是不对，改成角度，才过了，增量0.1，0.2就WA了，1S过的 = =。。。题意坑姐啊。。

后来用弧度制，一个一个试，增量0.003才过，0.004就WA。。。

刚搜了下题解，貌似有人推公式了！！！无比仰慕！！！http://www.cppblog.com/Uriel/articles/127186.html

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm><br /> using namespace std;<br /> const double pi = acos(-1.0);<br /> double d1,d2,r1,r2;<br /> bool solve()<br /> {<br /> double d = 0.0;<br /> double t1,t2;<br /> while( d*2 < pi )<br /> {<br /> t1 = r1*sin(d) + r2*cos(d);<br /> t2 = r1*cos(d) + r2*sin(d);<br /> if( ceil(t1) <= d1 && ceil(t2) <= d2 || ceil(t1) <= d2 && ceil(t2) <= d1 )<br /> return true;<br /> d += 0.003;<br /> }<br /> return false;<br /> }<br /> int main()<br /> {<br /> int ncases;<br /> scanf("%d",&ncases);<br /> while( ncases-- )<br /> {<br /> scanf("%lf%lf%lf%lf",&d1,&d2,&r1,&r2);<br /> if( solve() )<br /> printf("Escape is possible./n");<br /> else<br /> printf("Box cannot be dropped./n");<br /> }<br /> return 0;<br /> }<br />