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 Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Towers of Guard

Time limit: 1.0 second
Memory limit: 64 MB
Gondor is a land of hills. King of Gondor decided to build towers of guard on some of the hills for the protection of the kingdom. It turned out that the money available from the treasury was enough for constructing five towers only. The towers must be built at the vertices of a convex pentagon so that the wardens of the towers have a better view of the land. Gondor's King has a map of Gondor on which N hills are marked. Help King to choose five hills on which towers should be built.


The first line contains the number N of hills on the map of Gondor, 5 ≤ N ≤ 5000. In the next N lines the coordinates of the hills are given: (Xi, Yi). These are integers with absolute values not exceeding 108. No three hills belong to the same straight line.


Output «No» in the first line if you cannot choose five hills on which towers should be constructed. Otherwise, in the first line output «Yes» and in the second line give five different integers in the range from 1 to N, which are the numbers of the chosen hills in the counter-clockwise order. Separate the numbers with a space.


1 0
0 1
1 2
2 0
2 2
3 1
2 1 4 5 3
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1538. Towers of Guard