시간 제한메모리 제한제출정답맞은 사람정답 비율
1.5 초 1024 MB37242068.966%

문제

교준이는 이차원 좌표평면의 밤하늘을 바라보고 있다. 지금 하늘에는 서로 다른 위치에 $N$개의 별이 반짝이고 있고, $i$번 별의 위치는 $\left( X_i, Y_i \right)$이다.

교준이는 다음 조건을 모두 만족하도록 $N$개의 별을 두 개의 별자리, A 별자리와 B 별자리로 구분하고자 한다. 교준이가 사는 세상에서 별은 크기가 없는 고정된 점임에 유의하라.

  • 각 별은 A 별자리와 B 별자리 중에서 정확히 하나의 별자리에 속한다.
  • A 별자리 혹은 B 별자리에 속하는 별은 모두 교준이가 바라보고 있는 $N$개의 별 중 하나이다.
  • A 별자리와 B 별자리는 각각 적어도 하나의 별을 가진다.
  • A 별자리에 속한 별과 B 별자리에 속한 별을 서로 분리하는, $N$개의 별 중 어느 하나도 지나지 않는 밤하늘 위의 직선이 존재한다.

위의 조건을 모두 만족하도록 $N$개의 별을 A 별자리와 B 별자리로 구분하는 경우의 수를 구하라.

입력

첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 1\,500$)

둘째 줄부터 $N$개의 줄에 걸쳐, $N$개의 별에 대한 정보가 주어진다. $(i+1)$번째 줄에는 두 정수 $X_i$, $Y_i$가 주어진다. ($1 \le i \le N$, $\left| X_i \right| \le 10^8$, $\left| Y_i \right| \le 10^8$)

출력

첫째 줄에 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.

예제 입력 1

3
1 1
4 1
2 4

예제 출력 1

6

예제 입력 2

3
-1 -1
0 0
1 1

예제 출력 2

4

예제 입력 3

10
3 3
2 6
8 5
1 4
8 1
7 2
5 5
1 2
3 1
4 2

예제 출력 3

88

힌트

첫째 예제의 경우, 별을 구분하는 방법은 총 6가지다. 속이 찬 빨간 원과 속이 빈 파란 원은 각각 A 별자리와 B 별자리에 속하는 별을 의미한다.

마지막 예제를 그림으로 나타내면 아래와 같다.

출처

University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 - Division 1 B번