| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 71 | 30 | 27 | 40.909% |
인경호에는 인덕이와 안뇽이가 살고있다. 그러나 인경호는 형태가 복잡해서 정확한 영역을 측정하기 어려웠다. 그래서 두 친구는 $N$개의 꼭짓점을 가지는 단순 볼록 다각형을 인경호 둘레에 그려, 그 안쪽을 인경호의 영역으로 정했다. 그리고 $N$개의 꼭짓점마다 팻말을 세워 영역을 표시했다.
그러던 어느 날, 영역이 좁다고 불평하는 인덕이를 위해 안뇽이는 초능력을 사용해 팻말 중 하나를 옮겨 인경호를 확장해 주기로 했다. 하지만 팻말을 너무 멀리 옮기거나 인경호의 형태가 이상해지면 수상함을 감지한 인하대 학생들이 항의할 수 있기 때문에, 원래 위치에서 최대 $R$만큼 떨어진 곳까지만 단순 다각형을 유지하면서 옮기기로 하였다.
그러나 안뇽이는 인경호 지하 비밀기지를 정비하느라 너무 바쁘다. 안뇽이 대신 인경호를 최대 넓이로 만들기 위해 옮겨야하는 팻말의 번호와 옮겨야 하는 위치를 구해주자!
만약 최대 넓이를 만드는 것이 가능한 팻말이 여러 개라면, 안뇽이는 번호가 그 중 가장 작은 팻말을 옮긴다.
첫 번째 줄에 팻말의 수 $N$과 팻말을 옮길 수 있는 최대 거리인 정수 $R$이 공백으로 구분되어 주어진다.
이어서 $N$개의 줄에 걸쳐 두 정수 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. 이는 $i$번 팻말의 $x$좌표와 $y$좌표를 의미한다.
모든 팻말의 위치는 서로 다르며, 시계 방향 순서로 주어진다.
첫 번째 줄에 최대 넓이를 만들기 위해 옮겨야 하는 팻말의 번호를 출력한다.
두 번째 줄에 팻말을 옮겨야 하는 위치의 $x$좌표와 $y$좌표를 공백으로 구분하여 출력한다.
상대 오차 또는 절대 오차가 10ドル^{-9}$ 이내이면 정답으로 인정된다.
3 5 0 0 0 10 5 5
3 10 5
예제 1에서, 그림과 같이 3ドル$번 팻말을 $(10, 5)$로 옮겼을 때 인경호의 넓이가 50ドル$으로 최대가 된다.
4 4 0 -1 -2 -2 -1 0 1 1
1 2.82842712474619 -3.82842712474619
예제 2에서, 그림과 같이 1ドル$번 팻말을 $(2\sqrt{2}, -1-2\sqrt{2})$로 옮겼을 때 인경호의 넓이가 3ドル+6\sqrt{2}$로 최대가 된다.
단순 볼록 다각형은 다각형을 이루는 변들이 서로 교차하지 않고 내각의 크기가 모두 180ドル,円^{\circ}$ 미만인 다각형을 말한다.