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.
Input
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
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.
Sample
input | output |
---|
6
1 0
0 1
1 2
2 0
2 2
3 1
| Yes
2 1 4 5 3
|
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)