COCI '20 Contest 6 #4 Geometrija

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

You are given n points on the plane, such that no three points lie on the same line.

We say that line segments \overline{AB} and \overline{CD} cross if they share a point X different from the points A, B, C and D.

Let \mathcal S be the set of all line segments between pairs of the given points. Find the number of segments in \mathcal S that don't cross with any other segment in \mathcal S.

Input Specification

The first line contains an integer n (3 \le n \le 1\,000), 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 Specification

Output the requested number of segments.


1203 \le n \le 40
2303 \le n \le 200
360No additional constraints.

Sample Input 1

1 1
-1 1
-1 -1
1 -1

Sample Output 1


Sample Input 2

-1 -1
1 -1
0 1
0 0

Sample Output 2


Explanation for Sample Output 1 and 2


There are no comments at the moment.