Triangle regions
Time limit2sMemory limit512 MB
Given N points with no three collinear, count for each v how many triangles formed by three points contain exactly v other points strictly inside.
- Level
Hard8 of 10
- Topics
- Geometry, Combinatorics, Sorting, Two pointers
- Solved
- No attempts yet
Problem
A farmer wants to sell his land to raise cash. There are trees on the land, and each tree is one point in the coordinate plane. No three trees lie on a single straight line.
The farmer treats every triangular region whose corners are three different trees as a candidate for sale, so there are candidates in total.
The value of a candidate is set by , the number of trees inside the triangle with the corners excluded. Since no three trees are on one line, no tree lies on a side of a triangle either. For every from to , write a program that counts the triangular regions holding exactly trees inside.
Input
The first line contains the number of trees . ()
Each of the next lines contains two integers, the coordinate and the coordinate of one tree, separated by a space. ()
No three trees lie on a single straight line.
Output
Print lines. On line , print the number of triangular regions holding exactly trees inside.