[BOJ 23776] Jet Set
View as PDFYour wealthy friends love to brag about all their travelling. Every time you see them, they have visited some new exotic place you have never heard of. All of them are all too happy to tell you they have been all around the world---but you're not so sure about that. Have these jetsetters made a real circumnavigation?</p>
There exist many different definitions of what exactly constitutes a circumnavigation, but for the purposes of this problem we consider a circumnavigation a journey starting and ending at the same point and visiting all meridians (lines of longitude) along the way. Note that the North and South Pole are part of every meridian.

Figure 1: Illustration of Sample Input 1, giving a circumnavigation starting and ending in Reykjavík, with additional waypoints in Athens, Jakarta, Honolulu and Chicago.
Amelia, one of your rich friends, gave you a log of her flights in the form of a list of waypoints. Her trip started at the first waypoint, visited the remaining waypoints in order, and finally went back from the last waypoint to the first. Between consecutive waypoints, Amelia always travelled along the shortest circular arc connecting the two points. Find out whether Amelia's trip can be considered a circumnavigation in the above sense, and if not find a meridian that Amelia never visited. In that case, always report exactly an integer-valued or half-integer-valued meridian.
입력 형식
The input consists of:</p>
- One line with an integer $n$ ($2 \le n \le 1\,000$), the number of waypoints.
- $n$ lines, each with two integers $\phi$ and $\lambda$ ($-90 < \phi < 90, -180 \le \lambda < 180$), the latitude and longitude of one of the waypoints.
No two consecutive waypoints along the route are equal or antipodes (opposite points on the sphere) of each other.
출력 형식
If the route is a valid circumnavigation, output yes. Otherwise, output no, followed by a longitude $\lambda$ ($-180 \le \lambda < 180$) which the route never visited. The longitude must end in either .0 or .5.
예제 입력 1
5
64 -22
38 24
-6 107
21 -158
42 -88
예제 출력 1
yes
예제 입력 2
2
80 30
75 -150
예제 출력 2
yes
예제 입력 3
4
45 0
0 -170
-45 0
0 170
예제 출력 3
no 173.5
Comments