UVA427 FlatLand Piano Movers 题解
UVA427 FlatLand Piano Movers
题目描述
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=368
输入格式
输出格式
输入输出样例 #1
输入 #1
600,200 300,500 837,500 350,350 137,1200 600,500 600,400输出 #1
YYN YNSolution
题目描述
一台钢琴要在窄走廊中进行多次直角转弯；
钢琴的长宽和走廊转弯前后的宽度已知，钢琴的俯视图为矩形，转弯依靠拉动矩形的短边来完成；
一组测试数据为一行，一行中包含多组形如( x , y ) (x,y)(x,y)的逗号分隔的二元组，第一个二元组表示钢琴的长宽，此后的多个二元组表示走廊的尺寸。
对于每一组数据，判断钢琴能不能通过每一个转角，如果能，输出Y \text{Y}Y，否则输出X \text{X}X。
分析
本题属于具有一定思维含量的几何问题。钢琴进行直角转弯的流程可以用下图来描述。
上图中，w 1 , w 2 w_1,w_2w1,w2表示转弯前后走廊的宽度，L LL表示钢琴的长度，W WW表示钢琴的宽度。p 1 , p 2 p_1,p_2p1,p2表示钢琴两个顶点与外侧墙壁的接触点，C CC点表示走廊内侧的顶点，d dd表示这个顶点到钢琴另一边的直线距离。
注意到p 1 , p 2 p_1,p_2p1,p2和原点构成了一个直角三角形，因此
x 2 + y 2 = L 2 x^2+y^2=L^2x2+y2=L2
距离d dd可以借助三角形p 1 p 2 c p_1p_2cp1p2c的面积来求得，只有当d ≥ W d\ge Wd≥W时，钢琴才能转弯，因此
d = 2 A p 1 p 2 c / L = x y − w 1 y + w 2 x L ≥ W d=2A_{p_1p_2c}/L=\dfrac{xy-w_1y+w_2x}{L} \ge Wd=2Ap1p2c/L=Lxy−w1y+w2x≥W
联立上面两个式子，可以得到一个用于判定能否通过的不等式
f ( x ) = ( w 1 − x ) L 2 − x 2 + w 2 x − W L ≥ 0 f(x)=(w_1-x)\sqrt{L^2-x^2}+w_2x-WL\ge 0f(x)=(w1−x)L2−x2+w2x−WL≥0
其中0 ≤ x ≤ L 0\le x\le L0≤x≤L。上述不等式成立说明可以转弯，否则不能。注意到函数f ( x ) f(x)f(x)不具有单调性，因此并不能用二分查找来进行求解。注意到函数的几何曲线为凸性函数，具有极值，可以使用三分搜索法来求函数的极值。
三分查找和二分查找类似，其原理是将区间三等分，每次三分，会确定答案出现在左边一段，中间一段还是右边的一段。对于区间[ l , r ] [l,r][l,r]而言：
左三等分点在l 3 = ( 2 l + r ) / 3 l_3=(2l+r)/3l3=(2l+r)/3；
有三等分点在r 3 = ( l + 2 r ) / 3 r_3=(l+2r)/3r3=(l+2r)/3位置处；
对于给定的函数f ( x ) f(x)f(x)，计算f ( l 3 ) f(l_3)f(l3)和f ( r 3 ) f(r_3)f(r3)的值，若…
f ( l 3 ) < f ( r 3 ) f(l_3)<f(r_3)f(l3)<f(r3)，表明最小值不可能在右区间[ r 3 , r ] [r_3,r][r3,r]，应该继续在左区间中寻找最大值，同时更新r ← r 3 r \leftarrow r_3r←r3，缩小区间范围；
f ( l 3 ) > f ( r 3 ) f(l_3)>f(r_3)f(l3)>f(r3)，表明最小值不可能在左区间[ l , l 3 ] [l,l_3][l,l3]，应该继续在右区间中寻找最大值，同时更新l ← l 3 l \leftarrow l_3l←l3，缩小区间范围；
f ( l 3 ) = f ( r 3 ) f(l_3)=f(r_3)f(l3)=f(r3)，表明最值出现在中间的区间[ l 3 , r 3 ] [l_3,r_3][l3,r3]中，两边同时卡范围。
按照上述思路不断缩小范围达到需要的精度即可。
参考代码
#include<iostream>#include<fstream>#include<cmath>#include<sstream>usingnamespacestd;doubleeps=1e-10,len,width,w1,w2;charc;inlinedoublejudge(doublex){returnsqrt(len*len-x*x)*(w1-x)+w2*x-len*width;}intmain(){string line;while(getline(cin,line)){istringstreamiss(line);iss>>len>>c>>width;if(len<width)swap(len,width);while(iss>>w1>>c>>w2){doubleleft=0,right=len;while(fabs(left-right)>eps){doublel3=left+(right-left)/3.0;doubler3=right-(right-left)/3.0;judge(l3)>judge(r3)?left=l3:right=r3;}cout<<(judge(left)>=0?'Y':'N');}cout<<endl;}return0;}Extra
Part 1
f ( x ) = L 2 − x 2 ( w 1 − x ) − L W + w 2 x f(x)=\sqrt{L^2-x^2}(w_1-x)-L W+w_2 xf(x)=L2−x2(w1−x)−LW+w2x
对上述函数求导得到
f ′ ( x ) = − L 2 − x 2 − x ( w 1 − x ) L 2 − x 2 + w 2 f'(x)=-\sqrt{L^2-x^2}-\dfrac{x(w_1-x)}{\sqrt{L^2-x^2}}+w_2f′(x)=−L2−x2−L2−x2x(w1−x)+w2
和这道题类似，上述表达式的分母中出现的L 2 − x 2 \sqrt{L^2-x^2}L2−x2使得本题不适用牛顿法求解。
Part 2
本题描述的场景在现实生活中的一个典例是驾照 C1/C2 证科目二的“直角转弯”项目。题目中的钢琴蹭墙在对应着科目二直角转弯的“车轮轧线”，会被当场扣 100 分考试不合格。