Journey#2430
The renowned navigator Ferdinand Magellan has planned an adventurous journey. For this expedition, he has marked several points on the globe that he intends to visit in a specific order. Ferdinand will travel from one point to the next along the shortest possible path (assuming he can always navigate this path with his ship). The globe is modeled as a perfect sphere.
Your task is to determine whether his route will intersect itself, meaning if there will be any point that Ferdinand passes through more than once. Note that the end of one segment and the start of the next coincide and do not count as a self-intersection. It is also allowed for the start and end of the entire journey to coincide without being considered an intersection.
The first line contains an integer (1 \leq N \leq 5000), representing the number of points Ferdinand must visit in sequence. Each of the following lines contains integers, specifying the coordinates of each point: latitude ranging from to (positive for the northern hemisphere, negative for the southern) and longitude ranging from to (positive for the eastern hemisphere, negative for the western). It is guaranteed that consecutive points are not diametrically opposite.
Print YES if the route intersects itself, and NO otherwise.
Esempio 1