Little Nina is learning to read. Her favorite letter is N, and she looks for it everywhere.

There is a set of $N$ points on the plane. Let's consider four different points from the set and name them $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$ (in that order). Nina says that these four points form the letter N if all the following conditions are met:

$\mbox{A}$ is located strictly to the right of ray $\overrightarrow{BC}$ (in this order).
$\mbox{D}$ is located strictly to the left of ray $\overrightarrow{BC}$ (in this order).
Angle $\angle ABC\leq90^{\circ}$ 
Angle $\angle BCD\leq90\text{°}$

How many Ns can she find? We consider letters to be sets of four points, and two letters differ if the value of one or more of the points (i.e., $A,B,C$, or $\mbox{D}$) differs between the two corresponding sets of points. For example, if two sets of points have differing $\mbox{A}$ values, then they are different letters. In addition, letters that can be transformed into each other only by reversing point order are considered to be the same letter. 

Input Format

The first line contains a single integer, $N$, denoting the number of points. 

Each line $\boldsymbol{i}$ of the $N$ subsequent lines contain two space-separated integers, $x_i$ and $y_i$, describing the respective coordinates of point $(x_i,y_i)$. No two points coincide.

Constraints

$4\leq N\leq2318$
$-10^4\leq x_i,y_i\leq10^4$

Output Format

Print a single integer denoting the number of different Ns.

Sample Input
4
0 0
0 2
2 0
2 2

Sample Output
2

Explanation

To make this easier to read, we'll label our points as $P_1=(0,0)$, $P_2=(0,2)$, $P_3=(2,0)$, and $P_4=(2,2)$.

There are two different letter Ns:

$A,B,C,D=\{P_1,P_2,P_3,P_4\}$
$A,B,C,D=\{P_2,P_4,P_1,P_3\}$

Sets $\{P_1,P_3,P_2,P_4\}$ and $\{P_2,P_1,P_4,P_3\}$ (as well as their reversed variants) don't meet conditions $1$ and $2$ (we get a reversed N, like the Russian letter И).

Sets $\{P_4,P_3,P_2,P_1\}$ and $\{P_3,P_1,P_4,P_2\}$ are reversed variants of $1$ and $2$, so we don't add them to our answer.

Source: hackerrank | Difficulty: HARD
Tags: Geometry


Solutions:
from math import atan2
from sys import stderr
from time import process_time
from array import array

def readcase():
	n = int(input())
	return [[int(fld) for fld in input().strip().split()] for _ in range(n)]

def countns(pts):
	legcnt = []
	for i in range(len(pts)):
		legcnt.append(countlegs(pts, i))
	total = 0
	for i in range(len(pts)):
		for j in range(i):
			total += legcnt[i][j] * legcnt[j][i]
	return total

def countlegs(pts, i):
	ret = array('I', [0] * len(pts))
	vec = samedirclass(getvec(pts, i))
	nvec = len(vec)
	cnt = j = 0
	for (i, current) in enumerate(vec):
		if j == i:
			j = (j + 1) % nvec
			cnt = 0
		else:
			cnt -= len(current[2])
		while canbeleg(current, vec[j]):
			cnt += len(vec[j][2])
			j = (j + 1) % nvec
		for k in current[2]:
			ret[k] = cnt
	return ret

def getvec(pts, bi):
	(bx, by) = pts[bi]
	vec = []
	for (i, p) in enumerate(pts):
		if i == bi:
			continue
		(vx, vy) = (p[0] - bx, p[1] - by)
		if vx > 0:
			ang = (4, -vy / vx)
		elif vx < 0:
			ang = (2, -vy / vx)
		elif vy > 0:
			ang = (3, 0)
		else:
			ang = (1, 0)
		vec.append((ang, vx, vy, i))
	vec.sort()
	return vec

def samedirclass(vec):
	(a, cx, cy, i) = vec[0]
	inds = [i]
	current = [cx, cy, inds]
	ret = [current]
	for v in vec[1:]:
		(a, vx, vy, i) = v
		if cx * vy == cy * vx and cx * vx + cy * vy > 0:
			inds.append(i)
		else:
			inds = [i]
			current = [vx, vy, inds]
			ret.append(current)
			(cx, cy) = (vx, vy)
	return ret

def canbeleg(a, b):
	(ax, ay) = a[:2]
	(bx, by) = b[:2]
	return ay * bx > ax * by and ax * bx + ay * by >= 0

def BFIcountns(pts):
	total = 0
	for (i, b) in enumerate(pts):
		for j in range(i):
			c = pts[j]
			total += countnpart(pts, b, c) * countnpart(pts, c, b)
	return total

def countnpart(pts, b, c):
	count = 0
	(cx, cy) = (c[0] - b[0], c[1] - b[1])
	for p in pts:
		if p == b or p == c:
			continue
		(px, py) = (p[0] - b[0], p[1] - b[1])
		if px * cx + py * cy >= 0 and px * cy - py * cx > 0:
			count += 1
	return count
start = process_time()
print(countns(readcase()))
print(process_time() - start, file=stderr)