울타리 침공
시간 제한5초메모리 제한512 MB
주어진 점들 중 3개 이상을 골라 만들 수 있는 서로 다른 볼록 껍질 다각형의 개수를 10^9+7로 나눈 나머지를 구한다.
문제
알고리즘으로 이름난 코더가 어느 과학고에 있다. 그는 알고리즘을 으로 줄이고, 어려운 문제도 보자마자 풀어낸다.
이웃 과학고의 프로그래밍 동아리만은 그 실력을 인정하지 않았다. 소식을 들은 코더는 실력을 보여주려고 그 학교로 쳐들어가 손쉽게 항복을 받아냈다. 그래도 분이 풀리지 않아 학교 둘레에 자기 핸들을 새긴 울타리를 둘러 위세를 떨치기로 했다.
학교 주변에는 말뚝을 꽂을 수 있는 지점이 개 있다. 코더는 이 지점 중 3개 이상을 골라 그 자리에 말뚝을 꽂고, 말뚝이 이루는 볼록 껍질(convex hull) 모양으로 울타리를 친다. 돈도 시간도 많으니 만들 수 있는 울타리 모양을 하루에 하나씩 전부 만들 생각이다.
서로 다른 울타리 모양이 몇 가지인지 세어라. 두 울타리가 평면에서 같은 영역을 덮으면 같은 모양으로 본다.
입력
첫 줄에 말뚝을 꽂을 수 있는 지점의 수 ()이 주어진다.
다음 개 줄에는 각 지점의 정수 좌표 와 가 공백을 사이에 두고 주어진다. ()
세 지점이 한 직선 위에 있는 경우는 없다.
출력
첫 줄에 서로 다른 울타리 모양의 개수를 로 나눈 나머지를 출력한다.