Problem6465--共线问题

6465: 共线问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

在一个二维坐标平面上,给 $n\ (3 \leq n \leq 10^3)$ 个点,第 $i$ 个点的坐标为 $(x_i, y_i)\ (-10^9 \leq x_i, y_i \leq 10^9)$。
问有几对三点共线。

Input

第一行输入一个整数 $n$。
接下来 $n$ 行,每行两个整数。第 $i$ 行表示第 $i$ 个点的坐标。

Output

一行一个整数,表示有多少个三点共线。

Sample 1 Input

8
0 0
1 1
2 2
3 3
3 2
4 2
5 1
4 4

Sample 1 Output

12
以 $(0,0)$ 为起点:$(0,0),\ (1,1),\ (2,2)$,$(0,0),\ (1,1),\ (3,3)$,$(0,0),\ (1,1),\ (4,4)$,$(0,0),\ (2,2),\ (3,3)$,$(0,0),\ (2,2),\ (4,4)$,$(0,0),\ (3,3),\ (4,4)$
以 $(1,1)$ 为起点:$(1,1),\ (2,2),\ (3,3)$,$(1,1),\ (2,2),\ (4,4)$,$(1,1),\ (3,3),\ (4,4)$
以 $(2,2)$ 为起点:$(2,2),\ (3,3),\ (4,4)$,$(2,2),\ (3,2),\ (4,2)$
以 $(3,3)$ 为起点:$(3,3),\ (4,2),\ (5,1)$
这样一共合计 $12$ 个。

Source/Category

计算几何