최대 꼭짓점 볼록 다각형

시간 제한1초메모리 제한128 MB

요약
최대 100개의 점과 원점을 이용해 세 꼭짓점이 일직선이 되지 않도록 하면서 꼭짓점 개수가 최대인 볼록다각형을 찾는 문제입니다.
난이도

보통10점 중 7점

유형
동적 계획법, 기하, 정렬
정답자
아직 제출이 없습니다

문제

평면 위에 좌표가 모두 자연수인 점 N개가 주어진다. 원점 (0, 0)과 주어진 점들 중 일부를 꼭짓점으로 하는 볼록 다각형 중에서, 꼭짓점의 개수가 가장 많은 것을 찾으려고 한다. 이때 원점 (0, 0)은 반드시 그 다각형의 꼭짓점 중 하나여야 한다.

이러한 볼록 다각형의 꼭짓점 개수를 구하는 프로그램을 작성하시오.

다각형이 볼록이라는 것은, 다각형 내부에 있는 임의의 두 점을 잇는 선분이 항상 다각형 내부에 완전히 포함된다는 뜻이다.

다각형에서 이웃한 두 변은 서로 평행할 수 없다. 즉, 연속한 세 꼭짓점이 한 직선 위에 있어서는 안 된다.

입력

첫째 줄에 점의 개수를 나타내는 자연수 N이 주어진다 (2≤N≤1002 \le N \le 100).

다음 N개의 줄에는 각 점의 좌표를 나타내는 두 자연수 X와 Y가 공백 하나로 구분되어 주어진다 (1≤X≤1001 \le X \le 100, 1≤Y≤1001 \le Y \le 100). 주어지는 모든 점은 서로 다르다.

출력

꼭짓점의 개수가 가장 많은 볼록 다각형의 꼭짓점 개수를 첫째 줄에 출력한다.

참고: 정답은 항상 3 이상이다.

예제3

  1. 예제 1

    입력
    5
    4 2
    2 2
    2 3
    3 2
    3 1
    
    예상 출력
    4
    
  2. 예제 2

    입력
    8
    10 8
    3 9
    2 8
    2 3
    9 2
    9 10
    10 3
    8 10
    
    예상 출력
    8
    
  3. 예제 3

    입력
    10
    9 6
    1 7
    2 2
    3 9
    8 7
    3 2
    9 4
    3 1
    9 7
    6 9
    
    예상 출력
    7