Большой батут
Большой батут
Финес и Ферб хотят построить большой батут. Они уже построили n опор для батута, и теперь хотят его натянуть. При взгляде сверху, каждая опора является точкой на плоскости. Батут будет являться простым многоугольником с вершинами в этих точках. Простой многоугольник это многоугольник, граница которого не имеет самопересечений и самокасаний. Ребята хотят, чтобы батут имел наибольшую возможную площадь. И при этом, они хотят использовать каждую опору. Помогите им выбрать порядок, в котором опоры должны встречаться на границе батута, чтобы он представлял из себя простой многоугольник и имел наибольшую возможную площадь.
Входные данные
В первой строке дано одно целое число n (3 ≤ n ≤ 9) - количество опор для батута. В следующих n строках даны по два целых числа xi
и yi
(-108
≤ xi
, yi
≤ 108
) - координаты i-й опоры. Гарантируется, что никакие две точки не совпадают.
Выходные данные
Если невозможно построить простой многоугольник, вершинами которого будут являться дан-ные точки, в единственной строке выведите "No". Иначе, в первой строке выведите "Yes", а в следующей строке выведите перестановку чисел от 1 до n порядок, в котором опоры должны идти по границе батута.
5 0 0 2 2 -2 -2 2 -2 -2 2
Yes 1 2 4 3 5