New Year and Castle Construction
Time limit3sMemory limit512 MB
Given n points with no three collinear, count over all points p the number of 4-point subsets whose convex quadrilateral strictly contains p, and sum these counts.
- Level
Hard8 of 10
- Topics
- Geometry, Combinatorics, Sorting, Two pointers
- Solved
- No attempts yet
Problem
Kiwon's favorite video game is holding a new year event to motivate its users. The game is about building and defending a castle, and this led Kiwon to think about the following puzzle.
In a 2-dimensional plane, there is a set consisting of distinct points. In the set , no three distinct points lie on a single line. For a point , we can protect this point by building a castle. A castle is a simple quadrilateral (a polygon with vertices) that strictly encloses the point (that is, the point lies strictly inside the quadrilateral).
Kiwon is interested in the number of -point subsets of that can be used to build a castle protecting . If a single subset can be connected in more than one way to enclose a point, it is counted only once.
Let be the number of -point subsets that can enclose the point . Compute the sum of over all points .
Input
The first line contains a single integer ().
The next lines each contain two integers and , the coordinates of a point ().
All points are distinct, and no three points are collinear.
Output
Print the sum of over all points .