Problem 1016 无归之室

来源:http://acm.fzu.edu.cn/problem.php?pid=1016

Problem Description
金字塔中有一个房间名叫“无归之室”。房间地面完全由相同的矩形瓷砖覆盖。房间里布满无数的机关和陷阱,这正是其名字的由来。考古队花了几年时间研究对策,最后他们想出了一个方案。一台遥控的机器人将被送入房间,解除所有机关,然后返回。为了不触动机关,机器人必须走在瓷砖的中心区域上,绝对不能碰到瓷砖的边缘。如果走错一步,机器人会被落下的岩石砸成薄饼。

当考古队正准备行动的时候,他们发现了一件可怕的事情:他们没有考虑到机器人携带的工具箱。由于机器人必须将工具箱放在地面上才能开始解除机关,工具箱不可碰到瓷砖的边缘。现在他们急需你编程判断工具箱可否放下。

Input
输入文件有多组数据组成。每组数据仅含一行A, B, X, Y (1<=A, B, X, Y<=50000,均为实数)。A, B为瓷砖的长和宽,X, Y为工具箱底面的长和宽(工具箱为长方体)。最后一组数据A=B=X=Y=0,标志文件结束,不需要处理。
Output
若工具箱能以某种方式放在地上,则输出”Escape is possible.”,否则输出”Box cannot be dropped.”。

1
2
3
4
5
6
7
Sample Input
10 10 8 8
8 8 10 10
0 0 0 0
Sample Output
Escape is possible.
Box cannot be dropped.

思路:这题卡了很久。。公式自己参考了别人的,也自己用自己的方法重新写了一遍,首先情况有3种 长宽 都小于 输出 Escape is possible. 。箱子的矩形的对角线大于砖块矩形的对角线,输出 Box cannot be dropped. 第三种情况就要计算了
我把砖块的矩形设置为 A 、B 箱子的矩形设置为 C、D 数据都预处理过 A 一定大于B 、C一定大于D。
我先假设不知道A利用 BCD计算出一个A的最小值A’,如果 A’小于A则说明可以放得下
如图:

做2条黄色辅助线。 勾股定理求对角线E,同样可以用勾股定理求线段L,再用相似三角形求出D/L=(B-Y)/x=(c-x)/y 可以推出公式,
设q=D/L (可以算出数值)

y=(cq - b) / (qq - 1)
求出Y后可以求出x 即可知道C-x 和 B-y ,可以求出绿色小三角形面积为 :

(C-x)D /2 再除以底线l 即(b-y) 得到三角形的高h。
2
h+L 就是我们所求的B’

下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cmath>
using namespace std;
void changeab(double &a, double &b) {
if (a<b) {
double c = b;
b = a; a = c;
}
}
int main() {
double a, b, c, d;
while (cin >> a >> b >> c >> d&&a != 0&&b!=0&&c!=0&&d!=0) {
changeab(a, b);
changeab(c, d);
if (c < a&&d < b) {
cout << "Escape is possible." << endl;
}
else if (a*a + b*b<c*c + d*d) {
cout << "Box cannot be dropped." << endl;
}else{
double djxpf = c*c + d*d;
double p = sqrt(djxpf - b*b);
double q = d / p;
double y = (c*q - b) / (q*q - 1);
double l = b-y;
double bianb = sqrt(l*l - d*d);
double area = bianb*d;
double h = area / l;
if (p+2*h<a&&d<b) {
cout << "Escape is possible." << endl;
}else {
cout << "Box cannot be dropped." << endl;
}
}
}
return 0;
}