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: HARD
Tags: Geometry

Combinatorics

Sorting

Complete search

Mathematics

Data structures
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
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)


import random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter
input = sys.stdin.readline

def solution(li):
	n = len(li)
	co = n * (n - 1) * (n - 2) / 6
	for i in range(len(li)):
		(x, y) = li[i]
		ma = {}
		for j in range(i + 1, n):
			(x1, y1) = li[j]
			if x1 - x == 0:
				slope = 1e309
			else:
				slope = (y1 - y) / (x1 - x)
			if slope not in ma:
				ma[slope] = 0
			co -= ma[slope]
			ma[slope] += 1
	return int(co)

def input_test():
	li1 = []
	for _ in range(int(input())):
		li = list(map(int, input().strip().split(' ')))
		li1.append(li)
	out = solution(li1)
	print(out)

def test():
	pass
input_test()


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((1000000000.0 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)


from fractions import gcd
tot = 0
t = []
a = int(input())
for i in range(a):
	(x, y) = 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))


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()


import math
n = int(input())

def nc2(n):
	return n * (n - 1) // 2
points = []
ans = 0
for i in range(n):
	points.append(list(map(int, input().split())))
for i in range(n):
	dct = {}
	for j in range(i + 1, n):
		if i == j:
			continue
		a = points[i][1] - points[j][1]
		b = points[i][0] - points[j][0]
		x = math.gcd(a, b)
		a //= x
		b //= x
		if b < 0 or (b == 0 and a < 0):
			a *= -1
			b *= -1
		s = str(a) + '/' + str(b)
		if s in dct:
			dct[s] += 1
		else:
			dct[s] = 1
	ans += nc2(n - i - 1)
	for k in dct:
		ans -= nc2(dct[k])
print(ans)


import math
n = int(input())
c = []
l = []
for i in range(n):
	l.append(tuple(map(int, input().split())))
s = set(l.copy())
l.sort()
if n < 3:
	print(0)
else:
	ct = 0
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			ap = n - j - 1
			pta = l[i]
			ptb = l[j]
			rs = l[j][1] - l[i][1]
			rn = l[j][0] - l[i][0]
			g = math.gcd(rs, rn)
			rs //= g
			rn //= g
			x = l[j][0] + rn
			y = l[j][1] + rs
			while x <= 100 and y <= 100:
				if (x, y) in s:
					ap -= 1
				x += rn
				y += rs
			ct += ap
	print(ct)


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()


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():
	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) = 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)
main()


import sys
from math import gcd
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
ans = 0
for (xi, yi) in p:
	angle = defaultdict(int)
	for (x, y) in p:
		if xi == x and yi == y:
			continue
		x -= xi
		y -= yi
		if x < 0 or (x == 0 and y < 0):
			x = -x
			y = -y
		g = abs(gcd(x, y))
		x //= g
		y //= g
		angle[x, y] += 1
	cnt = 0
	for i in angle.keys():
		cnt += angle[i] * (n - 1 - angle[i])
	ans += cnt // 2
print(ans // 3)


n = int(input())
p = []
for _ in range(n):
	(x, y) = input().split()
	p.append((int(x), int(y)))
k = []
from math import gcd

def getk(x1, y1, x2, y2):
	if x1 == x2:
		return (1, 0)
	if y1 == y2:
		return (0, 1)
	num = y2 - y1
	den = x2 - x1
	g = gcd(abs(num), abs(den))
	num //= g
	den //= g
	if den < 0:
		num = -num
		den = -den
	return (num, den)
for i in range(n):
	tk = {}
	for j in range(n):
		if i == j:
			continue
		tmp = getk(*p[i], *p[j])
		tk[getk(*p[i], *p[j])] = tk.get(tmp, 0) + 1
	k.append(tk)
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ans += n - 1 - k[i][getk(*p[i], *p[j])]
print(ans // 3)


__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]) = 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
	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)


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 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
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()


n = int(input())
if n < 3:
	print(0)
else:
	ans = n * (n - 1) * (n - 2) / 6
	x = [0] * n
	y = [0] * n
	for i in range(n):
		(x[i], y[i]) = map(int, input().split())
	for i in range(n):
		seen = {}
		(x1, y1) = (x[i], y[i])
		for j in range(i + 1, n):
			(x2, y2) = (x[j], y[j])
			if x2 - x1 == 0:
				m = 1e309
			else:
				m = (y2 - y1) * 1.0 / (x2 - x1)
			if m not in seen:
				seen[m] = 0
			ans -= seen[m]
			seen[m] += 1
	print(int(ans))


def solve(dots, n):
	ans = n * (n - 1) * (n - 2) / 6
	for i in range(n):
		seen = {}
		for j in range(i + 1, n):
			if dots[i][0] - dots[j][0] == 0:
				e = 10 ** 10
			else:
				e = (dots[i][1] - dots[j][1]) / (dots[i][0] - dots[j][0])
			if e not in seen.keys():
				seen[e] = 0
			ans -= seen[e]
			seen[e] += 1
	return int(ans)

def main():
	n = int(input().strip())
	if n < 3:
		print(0)
	else:
		dots = []
		for _ in range(n):
			dots.append(list(map(int, input().strip().split())))
		print(solve(dots, n))
main()