UVA427 FlatLand Piano Movers 题解

UVA427 FlatLand Piano Movers题目描述Link: https://uva.onlinejudge.org/index.php?optioncom_onlinejudgeItemid8category6pageshow_problemproblem368PDF输入格式输出格式输入输出样例 #1输入 #1600,200 300,500 837,500 350,350 137,1200 600,500 600,400输出 #1YYN 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^2y^2L^2x2y2L2距离d dd可以借助三角形p 1 p 2 c p_1p_2cp1​p2​c的面积来求得只有当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 d2A_{p_1p_2c}/L\dfrac{xy-w_1yw_2x}{L} \ge Wd2Ap1​p2​c​/LLxy−w1​yw2​x​≥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​w2​x−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(2lr)/3l3​(2lr)/3有三等分点在r 3 ( l 2 r ) / 3 r_3(l2r)/3r3​(l2r)/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​]中两边同时卡范围。按照上述思路不断缩小范围达到需要的精度即可。参考代码#includeiostream#includefstream#includecmath#includesstreamusingnamespacestd;doubleeps1e-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);isslencwidth;if(lenwidth)swap(len,width);while(issw1cw2){doubleleft0,rightlen;while(fabs(left-right)eps){doublel3left(right-left)/3.0;doubler3right-(right-left)/3.0;judge(l3)judge(r3)?leftl3:rightr3;}cout(judge(left)0?Y:N);}coutendl;}return0;}ExtraPart 1f ( x ) L 2 − x 2 ( w 1 − x ) − L W w 2 x f(x)\sqrt{L^2-x^2}(w_1-x)-L Ww_2 xf(x)L2−x2​(w1​−x)−LWw2​x对上述函数求导得到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−x2​x(w1​−x)​w2​和这道题类似上述表达式的分母中出现的L 2 − x 2 \sqrt{L^2-x^2}L2−x2​使得本题不适用牛顿法求解。Part 2本题描述的场景在现实生活中的一个典例是驾照 C1/C2 证科目二的“直角转弯”项目。题目中的钢琴蹭墙在对应着科目二直角转弯的“车轮轧线”会被当场扣 100 分考试不合格。