시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
평면 위에 좌표가 모두 자연수인 점 N개가 주어진다. 원점 (0, 0)과 주어진 점들 중 일부를 꼭짓점으로 하는 볼록 다각형 중에서, 꼭짓점의 개수가 가장 많은 것을 찾으려고 한다. 이때 원점 (0, 0)은 반드시 그 다각형의 꼭짓점 중 하나여야 한다.
이러한 볼록 다각형의 꼭짓점 개수를 구하는 프로그램을 작성하시오.
다각형이 볼록이라는 것은, 다각형 내부에 있는 임의의 두 점을 잇는 선분이 항상 다각형 내부에 완전히 포함된다는 뜻이다.
다각형에서 이웃한 두 변은 서로 평행할 수 없다. 즉, 연속한 세 꼭짓점이 한 직선 위에 있어서는 안 된다.
첫째 줄에 점의 개수를 나타내는 자연수 N이 주어진다 (2≤N≤100).
다음 N개의 줄에는 각 점의 좌표를 나타내는 두 자연수 X와 Y가 공백 하나로 구분되어 주어진다 (1≤X≤100, 1≤Y≤100). 주어지는 모든 점은 서로 다르다.
꼭짓점의 개수가 가장 많은 볼록 다각형의 꼭짓점 개수를 첫째 줄에 출력한다.
참고: 정답은 항상 3 이상이다.