Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane. 

Next n lines contain two integers each x_{i}, y_{i} ( - 100 ≤ x_{i}, y_{i} ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.


-----Output-----

In the first line print an integer — the number of triangles with the non-zero area among the painted points.


-----Examples-----
Input
4
0 0
1 1
2 0
2 2

Output
3

Input
3
0 0
1 1
2 0

Output
1

Input
1
1 1

Output
0



-----Note-----

Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).

Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).

Note to the third sample test. A single point doesn't form a single triangle.

Difficulty: interview

Starter code:

Solutions:
from fractions import gcd
from collections import defaultdict

def read_data():
    n = int(input())
    points = []
    for i in range(n):
        x, y = map(int, input().split())
        points.append((x, y))
    return n, points

def solve(n, points):
    if n <= 2:
        return 0
    zeros = 0
    for i, (x, y) in enumerate(points[:-2]):
        zeros += count_zeros(i, x, y, points)
    return n * (n-1) * (n-2) // 6 - zeros

def count_zeros(i, x, y, points):
    slopes = defaultdict(int)
    for xj, yj in points[i + 1:]:
        dx = x - xj
        dy = y - yj
        d = gcd(dx, dy)
        slope = (dx/d, dy/d)
        slopes[slope] += 1
    zeros = 0
    for val in slopes.values():
        if val >= 2:
            zeros += val * (val - 1)
    return zeros // 2

n, points = read_data()
print(solve(n, points))

from fractions import gcd
tot = 0

t = []
a = int(input())
for i in range(a):
    x, y = list(map(int, input().split(' ')))
    t.append([x,y])


for i in t:
    slope = {}
    zd = 0
    oded = []
    for j in t:
        if j != i:
            if j[0] == i[0]:
                zd += 1
            else:
                f1 = (j[1]-i[1])
                f2 = (j[0]-i[0])
                gd = gcd(f1, f2)
                if gd == 0:
                    oded.append(987987987)
                
                else:
                    f1 //= gd
                    f2 //= gd
                    kk = f1*10000+f2
                    oded.append(kk)
    oded.sort()
    oded.append(-1000000)
    asdf = 0
    kk = [-1] + [ea for ea in range(len(oded)-1) if oded[ea] != oded[ea+1]]
    kk2 = [kk[i+1] - kk[i] for i in range(len(kk)-1)]

    for ii in kk2:
        tot += (ii*(ii-1)//2)
    tot+=(zd*(zd-1)//2)

tot //= 3
print(int(a*(a-1)*(a-2)//6-tot))


from fractions import *
n,s=int(input()),0
p=[tuple(map(int, input().split())) for _ in range(n)]
def f(a,b): g=gcd(a,b);return a//g + 1024*1024*(b//g)
for i in range(n):
    k,(x,y)=0,p[i]
    l=sorted(f(x-X, y-Y) for X,Y in p[:i])
    for j in range(1, i):
        k=k+1 if l[j]==l[j-1] else 0
        s+=k
print(n*(n-1)*(n-2)//6-s)


from fractions import *
n=int(input())
s=n*(n-1)*(n-2)//6
p=[tuple(map(int,input().split())) for _ in range(n)]
def f(a,b):g=gcd(a,b);return a//g+((b//g)<<20)
for i in range(n):
	k,(x,y)=0,p[i]
	l=sorted(f(x-X,y-Y) for X,Y in p[:i])
	for j in range(1, i):
		k=k+1 if l[j]==l[j-1] else 0
		s-=k
print(s)


from fractions import *
n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
f=lambda a,b:a//gcd(a,b)+(b//gcd(a,b)<<20)
for i in range(n):
	k,l=0,sorted(f(p[i][0]-X,p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)


from fractions import *
n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
	k,l=0,sorted(1e9 if p[i][1]==Y else (p[i][0]-X)/(p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)


n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
	k,l=0,sorted(1e9 if p[i][1]==Y else (p[i][0]-X)/(p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for x0, y0 in points:
        angles = defaultdict(int)
        for x, y in points:
            if x == x0 and y == y0:
                continue
            x -= x0
            y -= y0
            if x < 0 or x == 0 and y < 0:
                x = -x
                y = -y
            g = abs(gcd(x, y))
            x //= g
            y //= g
            angles[x * 1000000 + y] += 1
        t = 0
        for i in list(angles.keys()):
            t += angles[i] * (n - 1 - angles[i])
        result += t // 2
    
    print(result // 3)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    precalc_gcd = [[gcd(i, j) for j in range(201)] for i in range(201)]
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for x0, y0 in points:
        angles = defaultdict(int)
        for x, y in points:
            if x == x0 and y == y0:
                continue
            x -= x0
            y -= y0
            if x < 0 or x == 0 and y < 0:
                x = -x
                y = -y
            g = precalc_gcd[abs(x)][abs(y)]
            x //= g
            y //= g
            angles[x * 1000 + y] += 1
        t = 0
        for i in list(angles.keys()):
            t += angles[i] * (n - 1 - angles[i])
        result += t // 2
    
    print(result // 3)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    precalc_gcd = [[gcd(i, j) for j in range(201)] for i in range(201)]
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for x0, y0 in points:
        angles = defaultdict(int)
        for x, y in points:
            if x == x0 and y == y0:
                continue
            x -= x0
            y -= y0
            if x < 0 or x == 0 and y < 0:
                x = -x
                y = -y
            g = precalc_gcd[abs(x)][abs(y)]
            x //= g
            y //= g
            angles[x * 1000 + y] += 1
        for i in list(angles.keys()):
            result += angles[i] * (n - 1 - angles[i])
    
    print(result // 6)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    precalc_gcd = [[gcd(i, j) for j in range(201)] for i in range(201)]
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for i in range(n):
        x0, y0 = points[i]
        angles = defaultdict(int)
        for j in range(i + 1, n):
            x, y = points[j]
            x -= x0
            y -= y0
            if x < 0 or x == 0 and y < 0:
                x = -x
                y = -y
            g = precalc_gcd[abs(x)][abs(y)]
            x //= g
            y //= g
            angles[x * 1000 + y] += 1
        for j in list(angles.keys()):
            result += angles[j] * (n - i - 1 - angles[j])
    
    print(result // 2)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    precalc_gcd = [[gcd(i, j) for j in range(201)] for i in range(201)]
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for i in range(n):
        x0, y0 = points[i]
        angles = defaultdict(int)
        for j in range(i + 1, n):
            x, y = points[j]
            x -= x0
            y -= y0
            if x < 0 or x == 0 and y < 0:
                x = -x
                y = -y
            g = precalc_gcd[abs(x)][abs(y)]
            x //= g
            y //= g
            angles[x * 1000 + y] += 1
        for j in list(angles.values()):
            result += j * (n - i - 1 - j)
    
    print(result // 2)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            normalize[x][y] = nx * 1000 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    for i in range(n):
        x0, y0 = points[i]
        angles = defaultdict(int)
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] += 1
        for j in list(angles.values()):
            result += j * (n - i - 1 - j)
    
    print(result // 2)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = 0
    angles = [0] * 170000
    for i in range(n):
        x0, y0 = points[i]
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] += 1
        for j in range(i + 1, n):
            x, y = points[j]
            k = angles[normalize[x - x0][y - y0]]
            result += k * (n - i - 1 - k)
            angles[normalize[x - x0][y - y0]] = 0
    
    print(result // 2)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = n * (n - 1) * (n - 2) // 6
    angles = [0] * 170000
    for i in range(n):
        x0, y0 = points[i]
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] += 1
        for j in range(i + 1, n):
            x, y = points[j]
            k = angles[normalize[x - x0][y - y0]]
            result -= k * (k - 1) // 2
            angles[normalize[x - x0][y - y0]] = 0
    
    print(result)
        
        
    
main()


def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = n * (n - 1) * (n - 2) // 6
    angles = [0] * 170000
    for i in range(n):
        x0, y0 = points[i]
        for j in range(i + 1, n):
            x, y = points[j]
            v = normalize[x - x0][y - y0]
            result -= angles[v]
            angles[v] += 1
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] = 0
    
    print(result)
        
        
    
main()


from fractions import gcd
import sys

def solve():
    n = int(input())
    if n < 3:
        print(0)
        return
    xs, ys = list(), list()
    for i in range(n):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    mem = [0] * 2002
    for i in range(n):
        slopes = dict()
        x, y = xs[i], ys[i]
        for o in range(n):
            if o != i:
                xo, yo = xs[o], ys[o]
                xdiff, ydiff = x - xo, y - yo
                div = gcd(xdiff, ydiff)
                xdiff //= div
                ydiff //= div
                tup = (xdiff, ydiff)
                if tup in slopes:
                    slopes[tup] += 1
                else: slopes[tup] = 2
        for val in slopes:
            mem[slopes[val]] += 1
    for i in range(2, len(mem)):
        mem[i] //= i
    res = fact(n, 3)
    for i in range(3, len(mem)):
        res -= mem[i] * fact(i, 3)
    print(res)


def fact(n, k):
    large, small = max(k, n - k), min(k, n - k)
    res = 1
    for i in range(large + 1, n + 1): res *= i
    for i in range(2, small + 1): res //= i
    return res

    
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()

def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = n * (n - 1) * (n - 2) // 6
    angles = [0] * 170000
    for i in range(n):
        x0, y0 = points[i]
        for j in range(i + 1, n):
            x, y = points[j]
            v = normalize[x - x0][y - y0]
            result -= angles[v]
            angles[v] += 1
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] = 0
    
    sys.stdout.write(str(result))
        
        
    
main()

def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    points = [(tokens.pop(), tokens.pop()) for i in range(n)]
    
    result = n * (n - 1) * (n - 2) // 6
    angles = [0] * 162000
    for i in range(n):
        x0, y0 = points[i]
        for j in range(i + 1, n):
            x, y = points[j]
            v = normalize[x - x0][y - y0]
            result -= angles[v]
            angles[v] += 1
        for j in range(i + 1, n):
            x, y = points[j]
            angles[normalize[x - x0][y - y0]] = 0
    
    sys.stdout.write(str(result))
        
        
    
main()

def main():
    import sys
    from collections import defaultdict
    from fractions import gcd
    
    normalize = [[0] * 405 for i in range(405)]
    for x in range(-200, 201):
        for y in range(-200, 201):
            if x == 0 and y == 0:
                continue
            nx, ny = x, y
            g = abs(gcd(x, y))
            nx //= g
            ny //= g
            if nx < 0 or nx == 0 and ny < 0:
                nx = -nx
                ny = -ny
            nx += 200
            ny += 200
            normalize[x][y] = nx * 401 + ny
            
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n = tokens.pop()
    X = [0] * n
    Y = [0] * n
    for i in range(n):
        X[i], Y[i] = tokens.pop(), tokens.pop()
    
    result = n * (n - 1) * (n - 2) // 6
    angles = [0] * 170000
    for i in range(n):
        x0, y0 = X[i], Y[i]
        for j in range(i + 1, n):
            v = normalize[X[j] - x0][Y[j] - y0]
            result -= angles[v]
            angles[v] += 1
        for j in range(i + 1, n):
            angles[normalize[X[j] - x0][Y[j] - y0]] = 0
    
    print(result)
        
        
    
main()


__author__ = 'JS'
n = int(input())
k = [0] * 2015
X = [0] * 2015
Y = [0] * 2015
eps = 1e-12
for i in range (n):
    X[i], Y[i] = list(map(int, input().split(" ")))
ans = (n-2) * (n-1) * n // 6
sum = 0
for i in range (n):
    tot = 0
    cnt = 0
    for j in range (i+1, n):
        if X[i] != X[j]:
            k[tot] = (Y[j] - Y[i]) / (X[j] - X[i])
            tot += 1
        else:
            cnt += 1
    #cnt -= 1
    sum += (cnt - 1) * cnt // 2
    k = sorted(k[:tot]) + k[tot:]
    cnt = 1
    for j in range (1, tot):
        if abs(k[j] - k[j-1]) < eps:
           cnt += 1
        else:
            sum += (cnt - 1) * cnt // 2
            cnt = 1
    sum += (cnt -1) * cnt // 2
ans -= sum
print(ans)



def main():
    from math import gcd
    n, l, cache = int(input()), [], {(0, 0): 80400}
    result = n * (n - 1) * (n - 2) // 6
    for _ in range(n):
        cnt = {}
        newx, newy = list(map(int, input().split()))
        for x, y in l:
            x -= newx
            y -= newy
            u = cache.get((x, y))
            if u is None:
                u = gcd(x, y)
                u = cache[x, y] = 80400 + (x * 401 + y) // (u if x > 0 or not x and y > 0 else -u)
            cnt[u] = cnt.get(u, -1) + 1
            result -= cnt[u]
        l.append((newx, newy))
    print(result)


def __starting_point():
    main()

__starting_point()

n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
	k,l=0,sorted(1e9 if p[i][1]==Y else (p[i][0]-X)/(p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)



n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
	k,l=0,sorted(1e9 if p[i][1]==Y else (p[i][0]-X)/(p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)



n=int(input())
s=n*(n-1)*(n-2)//6
p=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
	k,l=0,sorted(1e9 if p[i][1]==Y else (p[i][0]-X)/(p[i][1]-Y)for X,Y in p[:i])
	for j in range(1,i):k=k+1 if l[j]==l[j-1]else 0;s-=k
print(s)