This page is still under construction.

Parts of this page are still being built. What you see may change.

New Year and Castle Construction

Time limit3sMemory limit512 MB

Summary
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 s={(x1,y1),(x2,y2),…,(xn,yn)}s = \{(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\} consisting of nn distinct points. In the set ss, no three distinct points lie on a single line. For a point p∈sp \in s, we can protect this point by building a castle. A castle is a simple quadrilateral (a polygon with 44 vertices) that strictly encloses the point pp (that is, the point pp lies strictly inside the quadrilateral).

Kiwon is interested in the number of 44-point subsets of ss that can be used to build a castle protecting pp. If a single subset can be connected in more than one way to enclose a point, it is counted only once.

Let f(p)f(p) be the number of 44-point subsets that can enclose the point pp. Compute the sum of f(p)f(p) over all points p∈sp \in s.

Input

The first line contains a single integer nn (5≤n≤2 5005 \le n \le 2\,500).

The next nn lines each contain two integers xix_i and yiy_i, the coordinates of a point (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9).

All points are distinct, and no three points are collinear.

Output

Print the sum of f(p)f(p) over all points p∈sp \in s.

Examples3

  1. Example 1

    Input
    5
    -1 0
    1 0
    -10 -1
    10 -1
    0 3
    
    Expected output
    2
    
  2. Example 2

    Input
    8
    0 1
    1 2
    2 2
    1 3
    0 -1
    -1 -2
    -2 -2
    -1 -3
    
    Expected output
    40
    
  3. Example 3

    Input
    10
    588634631 265299215
    -257682751 342279997
    527377039 82412729
    145077145 702473706
    276067232 912883502
    822614418 -514698233
    280281434 -41461635
    65985059 -827653144
    188538640 592896147
    -857422304 -529223472
    
    Expected output
    213