#P14724. [ICPC 2022 Seoul R] Empty Quadrilaterals
[ICPC 2022 Seoul R] Empty Quadrilaterals
Description
A quadrilateral is a polygon with exactly four distinct corners and four distinct sides, without any crossing between its sides. In this problem, you are given a set of points in the plane, no three of which are collinear, and asked to count the number of all quadrilaterals whose corners are members of the set and whose interior contains no other points in .
:::align{center}
:::
For example, assume that consists of five points as shown in the left of the figure above. There are nine distinct quadrilaterals in total whose corners are members of , while only one of them contains a point of in its interior, as in the right of the figure above. Therefore, there are exactly eight quadrilaterals satisfying the condition and your program must print out 8 as the correct answer.
Input Format
Your program is to read from standard input. The input starts with a line containing an integer (), where denotes the number of points in the set . In the following lines, each line consists of two integers, ranging from to , representing the coordinates of a point in . There are no three points in that are collinear.
Output Format
Your program is to write to standard output. Print exactly one line consisting of a single integer that represents the number of quadrilaterals whose corners are members of the set and whose interior contains no other points in .
5
0 0
2 4
6 2
6 -2
7 3
8
4
0 0
10 0
5 10
3 2
3
10
10 10
1 0
4 8
-1 -4
-7 -4
-3 2
5 -10
-10 -5
1 1
5 -3
170
京公网安备 11011102002149号