시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 37 | 3 | 2 | 6.897% |
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 ≤ n ≤ 1000), the number of points.
The following n lines contain integers xi and yi (−109 ≤ xi, yi ≤ 109), the coordinates of the points.
Output the requested number of segments.
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | 3 ≤ n ≤ 40 |
2 | 30 | 3 ≤ n ≤ 200 |
3 | 60 | No additional constraints. |
4 1 1 -1 1 -1 -1 1 -1
4
4 -1 -1 1 -1 0 1 0 0
6