P16389 [HackerRank] N letter
提高
题目描述

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.

输入格式

见题面

输出格式

见题面

样例输入
4 0 0 0 2 2 0 2 2
样例输出
2