시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 29 7 6 21.429%

문제

평면 상에 N개의 점이 있다.

여기서 3개의 점을 골라 삼각형을 만들었을 때, 이 삼각형 안에 다른 점들이 최대로 들어가면 이를 슈퍼 삼각형이라고 부른다. 이 때, 삼각형의 변이나 꼭짓점에 있는 점들도 삼각형 내부에 있는 것으로 간주한다.

주어진 점들을 가지고 슈퍼 삼각형을 형성하는 세 점을 찾으시오.

입력

첫 번째 줄에는 N(3 ≤ N ≤ 300)이 들어온다.

다음 N개의 줄에는 각 점의 좌표 xi, yi가 들어온다.

(단, 주어진 입력에는 평행하지 않은 세 개의 점이 적어도 한 쌍은 있다.)

출력

첫 번째 줄에 슈퍼 삼각형 안에 포함되는 점의 개수를 출력한다.

두 번째 줄에 슈퍼 삼각형을 이루는 세 점의 번호를 아무렇게나 출력한다.

예제 입력

6
1 3
2 3
2 1
3 1
3 2
4 4

예제 출력

5
1 4 6

힌트