아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Большой батут

시간 제한2초메모리 제한1024 MB

요약
점이 최대 9개 주어질 때 모든 점을 꼭짓점으로 하는 단순 다각형 중 넓이가 최대인 것을 찾아 순서를 출력한다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

Финес и Ферб хотят построить большой батут. Они уже построили nn опор для батута, и теперь хотят его натянуть. При взгляде сверху, каждая опора является точкой на плоскости. Батут будет являться простым многоугольником с вершинами в этих точках. Простой многоугольник это многоугольник, граница которого не имеет самопересечений и самокасаний. Ребята хотят, чтобы батут имел наибольшую возможную площадь. И при этом, они хотят использовать каждую опору. Помогите им выбрать порядок, в котором опоры должны встречаться на границе батута, чтобы он представлял из себя простой многоугольник и имел наибольшую возможную площадь.

입력

В первой строке дано одно целое число nn --- количество опор для батута (3≤n≤93 \le n \le 9). В следующих nn строках даны по два целых числа x_ix\_i и y_iy\_i --- координаты ii-й опоры (−108≤x_i,y_i≤108-{10}^8 \le x\_i, y\_i \le {10}^8). Гарантируется, что никакие две точки не совпадают.

출력

Если невозможно построить простой многоугольник, вершинами которого будут являться данные точки, в единственной строке выведите <<No>>. Иначе, в первой строке выведите <<Yes>>, а в следующей строке выведите перестановку чисел от 11 до nn --- порядок, в котором опоры должны идти по границе батута.

힌트

Рис. 2: Батут, который построили в примере.

예제1

  1. 예제 1

    입력
    5
    0 0
    2 2
    -2 -2
    2 -2
    -2 2
    
    예상 출력
    Yes
    1 2 4 3 5