프로그램 명: usa_fence
제한시간: 1.2 초

농부 존은 울타리를 치기 위해 N(5 <= N <= 250)개의 말뚝을 구입했다. 모두들 알다시피 울타리를 치는 가장 좋은 방법은 가장 많은 말뚝을 포함하는 볼록다각형 모양으로 치는 것이다. 존 역시 직선으로 구성된 격자 모양의 목초지에 위와 같은 방법으로 울타리를 치고 싶다.

N개의 말뚝의 좌표(1 <= x_i <= 1,000; 1 <= y_i <= 1,000)가 주어질 때, 가장 많은 말뚝을 포함하는 볼록다각형 모양 울타리에서 말뚝의 갯수는 몇개인지 구하는 프로그램을 작성하시오. 단, 3개 이상의 말뚝이 동일 선상에 있는 경우는 없다.

입력

첫째 줄에는 정수 N이 주어지고, 둘째 줄부터 N+1번째 줄까지는 말뚝의 좌표 x_i와, y_i 가 주어진다.

출력

첫째 줄에 말뚝을 가장 많이 포함하는 볼록다각형 모양 울타리를 쳤을 때, 말뚝의 갯수를 출력한다.

입출력 예 

입력 

6 
5 5 
2 3 
3 2 
1 5 
5 1 
1 1 

출력 

5

입력 예제 보충

하나의 직사각형에 2개의 점이 들어있는 모양이다.

출력 예제 보충

가장 많은 점을 포함한 볼록다각형은 좌표 (2,3), (3,2), (5,1), (5,5), (1,5)를 포함한 것이다. 
출처:usaco 2008 DEC gold
번역:shinism
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]