Under construction

Still being built. Things may change

Empty Quadrilaterals

Time limit2sMemory limit1024 MB

Summary
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 PP of nn points in the plane, no three of which are collinear. Count the quadrilaterals whose corners are members of PP and whose interior contains no other points of PP.

For example, if PP has five points as shown in the left figure, there are nine distinct quadrilaterals whose corners are members of PP. Only one of them contains a point of PP in its interior, as shown in the right figure. The answer is therefore 88.

Input

The first line contains an integer nn (1≤n≤3001 \le n \le 300), the number of points in PP. Each of the following nn lines contains two integers, the coordinates of one point in PP. Every coordinate is between −109-10^9 and 10910^9, inclusive. No three points in PP are collinear.

Output

Print one line containing a single integer: the number of quadrilaterals whose corners are members of PP and whose interior contains no other points of PP.

Examples3

  1. Example 1

    Input
    5
    0 0
    2 4
    6 2
    6 -2
    7 3
    
    Expected output
    8
    
  2. Example 2

    Input
    4
    0 0
    10 0
    5 10
    3 2
    
    Expected output
    3
    
  3. Example 3

    Input
    10
    10 10
    1 0
    4 8
    -1 -4
    -7 -4
    -3 2
    5 -10
    -10 -5
    1 1
    5 -3
    
    Expected output
    170