고대 공룡들이 남쪽에서 북쪽 방향으로걸어간 발자국들이 발견되었다.

아래 그림은 발견된 공룡 발자국들의 다양한 예이다.

발자국을 분석한 결과 모든 발자국은 하나의 발뒤꿈치와 k개의 발가락(k ≥ 2)을 가지며, 두 발가락 사이마다 골이 존재한다.

이를 바탕으로 위 그림의 발자국을 단순화시켜보면 아래와 같이 2k각형으로 표현이 된다.

발자국의 다각형에서 발뒤꿈치를 시작으로 반시계 방향으로 돌면 항상 첫 번째 발가락에서 좌회전,

첫 번째 골에서 우회전, 두 번째 발가락에서 좌회전, 두 번째 골에서 우회전, ……, k-1번째 골에서 우회전,

k번째 발가락에서 좌회전해서 발뒤꿈치로 돌아오게 된다.

또한 발뒤꿈치와 발가락을 선분으로 잇는 경우 다음 조건을 항상 만족한다.

① 해당 선분은 발자국의 다각형을 벗어나지 않는다.

② 해당 선분은 골을 지나지 않는다.

다음 그림은 발자국이 될 수 없는 다각형들의 예이다.

발자국이 발견된 일부 지역에서는 불행히도 정확한 발자국이 남아있지 않고 발자국 다각형의 꼭짓점이 될 수 있는 점들만 남아있다.

심지어 여기에는 발자국과 관련 없는 점들도 같이 남아있을수 있다.

각 점의 위치는 좌표 (x, y)로 표현되며, x값은 서쪽에서 동쪽으로 증가하고 y값은 남쪽에서 북쪽으로 증가한다.

다행히도 점들 중 가장 남쪽에 있는 점은 유일하며 발뒤꿈치가 된다.

다음 그림의 예에서 보면 (20, 5) 점(붉은점)이 가장 남쪽에 위치하므로 발뒤꿈치이다.

주어진 점들로 만들 수 있는 가장 많은발가락을 가진 발자국을 찾고 싶다.

아래는 위 그림에서 찾은 가장 많은 발가락을 가진 발자국의 한 예이다.

점들의 좌표를 입력으로 받아서, 가장 많은 발가락을 가진 발자국을 하나 찾은 뒤

찾은 다각형의 꼭짓점의 개수와 각 꼭짓점의 좌표를 출력하는 프로그램을 작성하라.

공룡발자국 timer 2000초 memory 512MB

공룡발자국 2000초 512MB