Under construction

Still being built. Things may change

Triangle regions

Time limit2sMemory limit512 MB

Summary
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 NN 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 (N3)\binom{N}{3} candidates in total.

The value of a candidate is set by vv, 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 vv from 00 to N−3N-3, write a program that counts the triangular regions holding exactly vv trees inside.

Input

The first line contains the number of trees NN. (3≤N≤3003 \le N \le 300)

Each of the next NN lines contains two integers, the xx coordinate and the yy coordinate of one tree, separated by a space. (0≤x,y≤1 000 0000 \le x, y \le 1\,000\,000)

No three trees lie on a single straight line.

Output

Print N−2N-2 lines. On line ii, print the number of triangular regions holding exactly i−1i-1 trees inside.

Examples2

  1. Example 1

    Input
    7
    3 6
    17 15
    13 15
    6 12
    9 1
    2 7
    10 19
    
    Expected output
    28
    6
    1
    0
    0
    
  2. Example 2

    Input
    4
    0 0
    10 0
    0 10
    2 2
    
    Expected output
    3
    1