COCI '20 Contest 6 #4 Geometrija
View as PDFYou are given  points on the plane, such that no three points lie on the same line.
We say that line segments  and 
 cross if they share a point 
 different from the points 
, 
, 
 and 
.
Let  be the set of all line segments between pairs of the given points. Find the number of segments in 
 that don't cross with any other segment in 
.
Input Specification
The first line contains an integer  
, the number of points.
The following  lines contain integers 
 and 
 
, the coordinates of the points.
Output Specification
Output the requested number of segments.
Constraints
| Subtask | Points | Constraints | 
|---|---|---|
| 1 | 20 | |
| 2 | 30 | |
| 3 | 60 | No additional constraints. | 
Sample Input 1
4
1 1
-1 1
-1 -1
1 -1
Sample Output 1
4
Sample Input 2
4
-1 -1
1 -1
0 1
0 0
Sample Output 2
6
Comments