trokut | 프로그래밍의 벗 PivotOJ
PivotOJ

trokut

시간 제한: 3000ms메모리 제한: 128MB출처: CHC 2006 Croatian Olympiad in InformaticsBOJ 3179

문제

There are N different points in a plane. 

We say that the triangle formed by some three points as corners is a super-triangle if the number of points inside this triangle is as large as possible. We consider the points in the corners or on the sides of the triangle as being inside the triangle. 

Write a program that will, among given points, find three points that form some super-triangle. 

입력

The first line of input contains an integer N, 3 ≤ N ≤ 300. 

Each of the following N lines contains two integers – the coordinates of one point. 

Note: the test data will be such that there will be at least three non-collinear points. 

출력

The first line of output should contain the number of points inside the super-triangle. 

The second line should contain three numbers – indices of the three corner points of the super-triangle, in any order.

예제

예제 1

입력
6
1 3
2 3
2 1
3 1
3 2
4 4
출력
5
1 4 6

예제 2

입력
9
1 1
2 2
3 3
2 1
3 2
3 1
4 2
4 1
5 1
출력
9
1 9 3

예제 3

입력
13
1 3
2 4
3 1
4 1
4 2
4 3
4 4
4 5
5 1
5 2
6 1
6 5
7 3
출력
9
3 11 8
이 문제는 채점 준비 중입니다. 테스트 데이터가 확보되면 제출이 가능합니다.