레이팅 미적용설명
You are given \(n\) points on the plane, such that no three points lie on the same line.
We say that line segments \(AB\) and \(CD\) cross if they share a point \(X\) different from the points \(A\), \(B\), \(C\)
and \(D\).
Let \(S\) be the set of all line segments between pairs of the given points. Find the number of segments in \(S\)
that don’t cross with any other segment in \(S\).
제약
입력 형식
The first line contains an integer \(n\) (\(3 \le n \le 1000\)), the number of points.
The following \(n\) lines contain integers \(x_{i}\) and \(y_{i}\) (−\(10^{9} \le x_{i}\), \(y_{i} \le 10^{9}\)), the coordinates of the points.
출력 형식
Output the requested number of segments.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(3 \le n \le 40\) |
2 | 30점 | \(3 \le n \le 200\) |
3 | 60점 | No additional constraints. |
예제 1
입력
4
1 1
-1 1
-1 -1
1 -1
출력
4
예제 2
입력
4
-1 -1
1 -1
0 1
0 0
출력
6
문제 정보