Courses

알고리즘

기하학

Module: 기하학

Problem

6 /7

안전한 길

Problem

<사업부> Petya 및 Vasya – 좋은 친구. 따라서 그들은 종종 서로를 방문합니다. 최근 Petya

<사업부> 운전 면허증을 가지고 그의 친구를 방문할 것입니다. 간단하게 하기 위해

<사업부> 그들이 사는 도시의 모든 길은 끝없는 직선이다. 교차로에서

<사업부> 두 개 이상의 도로가 교차로입니다. Petya와 Vasya의 집은 일부 근처에 있습니다

<사업부> 도시 도로이지만 교차로는 아닙니다.

<사업부> Petya는 집 근처 도로에서 여행을 시작합니다. 동시에 그는

중 하나를 선택할 수 있습니다. <사업부> 두 방향. Petya가 교차로에 접근하면 다른 곳으로 방향을 돌릴 수 있습니다.

<사업부> 그것을 통과하는 도로 또는 현재 도로를 따라 계속 운전하십시오. Petya는 그다지 좋지 않기 때문에

<사업부> 노련한 운전자, 그가 만드는 모든 회전은 그를 걱정하게 만듭니다. 그리고

<사업부> Petya의 흥분은 그가 회전하는 각도와 같습니다. 예를 들어,

<사업부> Petya의 직각 흥분은 90입니다.

덜 날카로운 회전으로 Petya는 덜 걱정하고 더 가파르게 — 더 강하게.

우리는 전체 경로에 대한 Petya의 흥분이 <사업부> 그가 움직이는 동안 회전해야 할 각도. 물론 Petya는 <사업부> 가능한 한 걱정을 덜 수 있는 경로를 선택하세요. <사업부> Petya가 경험할 최소한의 전체 흥분이 무엇인지 알아내도록 도와주세요. <사업부> Vasya의 집에 도착했습니다. <사업부> 입력 데이터 형식 <사업부> 입력 파일의 첫 번째 줄에는 정수 n(1 ≤ n ≤ 50)이 포함됩니다. 의 도로 수 <사업부> 도시. 다음 n줄에는 도로에 대한 설명이 포함됩니다. <사업부> 각 도로는 좌표로 제공되는 4개의 정수 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입니다.