Courses

算法

几何学

Module: 几何学

Problem

6 /7

安全的方式

Problem

<分区> 彼佳和瓦夏——好朋友们。因此，他们经常互相拜访。最近Petya

<分区> 拿到了驾照，打算去拜访他的朋友。为简单起见，我们假设

<分区> 他们居住的城市的所有道路都是无尽的直线。在十字路口

<分区> 两条或多条道路是十字路口。 Petya 和 Vasya 的房子位于一些附近

<分区> 城市道路，但不在十字路口。

<分区> 彼佳在他家附近的路上开始了他的旅程。同时，他可以任意选择

<分区> 两个方向。当 Petya 接近十字路口时，他可以转向任何其他

<分区> 通过它的道路或继续沿着当前的道路行驶。因为Petya不是很好

<分区> 一个经验丰富的司机，他的每一个转弯都让他担心。和

<分区> Petya 的兴奋度等于他转身的角度，以度为单位。例如，使用

<分区> Petya 的直角兴奋度是 90。

转弯不那么急，Petya 的担心就少了，而陡峭的 -mdash;更强。

我们会假设Petya在整条路线中的兴奋度等于 <分区> 他在运动过程中必须转动的角度。当然，Petya 想要 <分区> 走一条让他尽可能少担心的路线。 <分区> 帮助 Petya 找出他将体验到的最低总兴奋度是多少， <分区> 到达瓦夏的家。 <分区> 输入数据格式 <分区> 输入文件的第一行包含一个整数 n (1 ≤ n ≤ 50) —道路数量 <分区> 城市。接下来的 n 行包含道路的描述。 <分区> 每条道路由四个整数x1,y1,x2,y2描述，由坐标给定 <分区> 道路经过的两个不同点 (x1, y1) 和 (x2, y2)。 <分区> 保证没有两条路是相同的。接下来的两行包含 <分区> Petya 和 Vasya 的房屋坐标。保证每栋房子正好在一条路上， <分区> 还有 Petya 和 Vasya 住在不同的地方。 <分区> 输入文件中所有点的坐标都是整数，不超过100 <分区> 绝对值。 <分区>
输出格式 <分区> 在输出文件中打印一个数字——总角度（以度为单位） <分区> Petya 将不得不选择最佳路线。答案被认为是正确的，如果 <分区> 其相对或绝对误差不超过10−9。 <分区> 如果 Petya 不能到达 Vasya 的家，打印数字 −1。
例子
输入
<分区> 3 <分区> 0 0 2 0 <分区> 1 1 0 2 <分区> 1 2 3 2 <分区> -3 0 <分区> 3 2
结语
270.0

输入
<分区> 1 <分区> 0 0 2 0 <分区> 0 0 <分区> 20
结语
0.0

输入
<分区> 5 <分区> 0 0 1 0 <分区> 0 0 1 1 <分区> 0 0 0 1 <分区> 0 0 -1 1 <分区> 0 1 1 1 <分区> 50 <分区> 05
结语
90.0

<分区> 下图对应第一个例子。 Petya 转了两个 135 圈 <分区> 度，它的总波是270.