Problem J
Jet Set
Your 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?
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.
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.
Input
The input consists of:
-
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.
Output
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.
Sample Input 1 | Sample Output 1 |
---|---|
5 64 -22 38 24 -6 107 21 -158 42 -88 |
yes |
Sample Input 2 | Sample Output 2 |
---|---|
2 80 30 75 -150 |
yes |
Sample Input 3 | Sample Output 3 |
---|---|
4 45 0 0 -170 -45 0 0 170 |
no 173.5 |