아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

울타리 침공

시간 제한5초메모리 제한512 MB

요약
주어진 점들 중 3개 이상을 골라 만들 수 있는 서로 다른 볼록 껍질 다각형의 개수를 10^9+7로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

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

문제

알고리즘으로 이름난 코더가 어느 과학고에 있다. 그는 O(N3)O(N^3) 알고리즘을 O(N2)O(N^2)으로 줄이고, 어려운 문제도 보자마자 풀어낸다.

이웃 과학고의 프로그래밍 동아리만은 그 실력을 인정하지 않았다. 소식을 들은 코더는 실력을 보여주려고 그 학교로 쳐들어가 손쉽게 항복을 받아냈다. 그래도 분이 풀리지 않아 학교 둘레에 자기 핸들을 새긴 울타리를 둘러 위세를 떨치기로 했다.

학교 주변에는 말뚝을 꽂을 수 있는 지점이 NN개 있다. 코더는 이 지점 중 3개 이상을 골라 그 자리에 말뚝을 꽂고, 말뚝이 이루는 볼록 껍질(convex hull) 모양으로 울타리를 친다. 돈도 시간도 많으니 만들 수 있는 울타리 모양을 하루에 하나씩 전부 만들 생각이다.

서로 다른 울타리 모양이 몇 가지인지 세어라. 두 울타리가 평면에서 같은 영역을 덮으면 같은 모양으로 본다.

입력

첫 줄에 말뚝을 꽂을 수 있는 지점의 수 NN (3≤N≤3003 \le N \le 300)이 주어진다.

다음 NN개 줄에는 각 지점의 정수 좌표 xix_i와 yiy_i가 공백을 사이에 두고 주어진다. (∣xi∣,∣yi∣≤109|x_i|, |y_i| \le 10^9)

세 지점이 한 직선 위에 있는 경우는 없다.

출력

첫 줄에 서로 다른 울타리 모양의 개수를 109+710^9+7로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

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

    입력
    3
    0 0
    5 1
    2 7
    
    예상 출력
    1