삼각형
시간 제한3초메모리 제한128 MB
평면 위 최대 300개 점 중 일직선이 아닌 세 점을 골라, 경계를 포함해 가장 많은 점을 포함하는 삼각형을 찾는 문제입니다.
문제
평면에 N개의 점이 주어진다.
주어진 점 중 한 직선 위에 있지 않은 세 점을 고르면 삼각형을 만들 수 있다. 어떤 삼각형이 포함하는 주어진 점의 수가 가능한 한 많다면, 그 삼각형을 슈퍼 삼각형이라고 부른다. 삼각형의 변 위나 꼭짓점에 있는 점도 포함된 것으로 센다.
주어진 점들 중 세 점을 골라 슈퍼 삼각형을 만들고, 그 삼각형에 포함되는 점의 수를 구하라.
입력
첫째 줄에 점의 수 N(3 ≤ N ≤ 300)이 주어진다.
다음 N개의 줄에는 각 점의 좌표 xi, yi가 주어진다.
입력에는 한 직선 위에 있지 않은 세 점의 조합이 적어도 하나 존재한다.
출력
첫째 줄에 슈퍼 삼각형에 포함되는 주어진 점의 개수를 출력한다.
둘째 줄에 그 삼각형을 이루는 세 점의 번호를 공백으로 구분해 출력한다.
조건을 만족하는 답이 여러 개라면 아무거나 출력해도 된다.