ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Mammoth Hunt

Time limit: 1.0 second
Memory limit: 64 MB
The very last mammoth runs away from a group of primeval hunters. The hunters are fierce, hungry and are armed with bludgeons and stone axes. In order to escape from his pursuers, the mammoth tries to foul the trail. Its path is a polyline (not necessarily simple). Besides, all the pairs of adjacent segments of the polyline form acute angles (an angle of 0 degrees is also considered acute).
After the mammoth vanished, it turned out that it had made exactly N turns while running away. The points where the mammoth turned, as well as the points where the pursuit started and where the pursuit ended, are known. You are to determine one if the possible paths of the mammoth.


The first line contains a positive integer N not exceeding 2000. The next N + 2 lines contain the coordinates of polyline vertices (this polyline is the mammoth's path). All the coordinates are integers between −2000 and 2000. No two vertices of the polyline coincide.


Output NO if no polyline with vertices in the given points can be the mammoth's path. Otherwise, output YES in the first line, and the mammoth's path in the second line. The path is to be output as a sequence of point numbers (the points are numbered from 1 to N + 2 in the same order they were given in the input). If there are many solutions, output any of them.


0 0
1 1
1 2
2 0
1 3 4 2
0 0
0 1
0 2
0 3
1 3 2 4
Problem Author: Alexander Ipatov
Problem Source: USU Junior Contest, October 2007
To submit the solution for this problem go to the Problem set: 1578. Mammoth Hunt