시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 1024 MB | 92 | 41 | 33 | 45.205% |
교준이는 이차원 좌표평면의 밤하늘을 바라보고 있다. 지금 하늘에는 서로 다른 위치에 $N$개의 별이 반짝이고 있고, $i$번 별의 위치는 $\left( X_i, Y_i \right)$이다.
교준이는 다음 조건을 모두 만족하도록 $N$개의 별을 두 개의 별자리, A 별자리와 B 별자리로 구분하고자 한다. 교준이가 사는 세상에서 별은 크기가 없는 고정된 점임에 유의하라.
위의 조건을 모두 만족하도록 $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$로 나눈 나머지를 출력한다.
3 1 1 4 1 2 4
6
3 -1 -1 0 0 1 1
4
10 3 3 2 6 8 5 1 4 8 1 7 2 5 5 1 2 3 1 4 2
88
첫째 예제의 경우, 별을 구분하는 방법은 총 6가지다. 속이 찬 빨간 원과 속이 빈 파란 원은 각각 A 별자리와 B 별자리에 속하는 별을 의미한다.
마지막 예제를 그림으로 나타내면 아래와 같다.
University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 > Division 1 B번