Geometrija
레이팅 미적용의견: 0
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\).
Subtask 1 (20 points): \(3 \le n \le 40\)
Subtask 2 (30 points): \(3 \le n \le 200\)
Subtask 3 (60 points): No additional constraints.
The first line contains an integer \(n\) (\(3 \le n \le 1000\)), the number of points.
The following \(n\) lines contain integers \(x@@RISE_MATH_BLOCK_0@@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. |
4
1 1
-1 1
-1 -1
1 -1
4
4
-1 -1
1 -1
0 1
0 0
6
평가 및 의견
Geometrija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Geometrija