#P3223. 足球赛
足球赛
Description
NJU和PKU ACM-ICPC队的足球迷们打算进行一场足球赛。因为frkstyc在运动方面相当不济,所以当裁判(Ikki说:“这是句大实话。”)。但是因为他们找不到足够的人来凑足两个11人的队伍,他们决定来玩一个修改版本的点球决胜!
在通常的点球决胜里,球在罚出之前一定要放在禁区里一个划定的点上。但是对这些球迷来说,这个队守门员未免太没有挑战性了。所以现在允许主罚点球的球员对球的位置有更多的选择——在一条事先划定的线段上的任意位置都可以。
球员总是想仔细选择球的位置,使得球门对球的张角尽可能地大,那样就有更大的机会把球放进网窝里。在现实中,要让这个张角真的达到最大几乎是不可能的,因为人的感知看起来总是更能应付模糊的事情,而不是精确的东西。但是对于你,一个程序设计大赛的选手,应该不是什么难题,因为你有眼前的计算机来帮忙,只要你得到了球门的那条摆球的线段的位置的精确描述。
Input
输入包含多组测试数据。每组测试数据只有一行,包含四个点A、B、U和V的坐标。点的坐标用(
x,
y)
的形式给出,由空格分隔。四个点互不重合。A和B描述球门。两根门柱分别位于A和B。站在A处沿矢量AB→方向看时,球门朝向右侧。U和V描述摆球的线段。站在U处沿矢量UV→方向看时,A和B都在左侧。线段的一部分有可能在球场之外,这部分照样允许摆球。线段的一部分可能在球门后面,这部分是不允许摆球的。
点的坐标都由不超过10,000的非负整数组成。文件结束符(EOF)表示输入结束。
Output
对每组测试数据,在线段UV上找一个点P,使得在P处球门AB可以从正面看见,而且角∠APB最大。如果这样的P不存在,那么认为答案是0。用度数输出这个角,精确到小数点后三个数字。允许有0.001°的误差。
(36,89) (79,97) (11,88) (72,32)
56.167
Hint
样例的图示:
BA被延长到交UV于R。当球被放在UR时它处在球门后面,因此是不允许的。但是它可以放在RV上的任意位置。在所有的位置中,P使∠APB最大。P的坐标大约是(42.3679, 59.1950)。
Source
第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, frkstyc, Ikki提供文字
Translator
Yingchong SITU 'frkstyc'