Empty Quadrilaterals
Time limit2sMemory limit1024 MB
Count simple quadrilaterals on a point set with no three collinear whose interiors contain no other points, for up to 300 points.
- Level
Hard8 of 10
- Topics
- Geometry, Dynamic programming, Sorting, Divide and conquer
- Solved
- No attempts yet
Problem
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. Count the quadrilaterals whose corners are members of and whose interior contains no other points of .

For example, if has five points as shown in the left figure, there are nine distinct quadrilaterals whose corners are members of . Only one of them contains a point of in its interior, as shown in the right figure. The answer is therefore .
Input
The first line contains an integer (), the number of points in . Each of the following lines contains two integers, the coordinates of one point in . Every coordinate is between and , inclusive. No three points in are collinear.
Output
Print one line containing a single integer: the number of quadrilaterals whose corners are members of and whose interior contains no other points of .