← 返回题目列表

Codeforces · 1163/C2

C2. 动力传输(硬版)

中文机器翻译题面 查看原题

这个问题和上一个问题一样,但是有更大的约束。

那是一个周日的早晨,三个朋友 Selena、Shiro 和 Katie 决定去附近的发电站一趟(不要在家里尝试)。到达发电站后,猫们对由许多烟囱、电线杆和电线组成的大型输电系统印象深刻。因为它们是猫,所以它们发现那些东西很大。

车站入口处有一张地图,描述了复杂的布线系统。赛琳娜是三个朋友中数学最好的。他决定在笛卡尔平面上绘制地图。现在,每个极点都是某个坐标 $$$(x_i, y_i)$$$ 处的一个点。由于每个极点都是不同的,因此代表这些极点的所有点都是不同的。此外,每两个极都通过电线相互连接。导线是平面上双向无限的直线。如果同一条线上有两个以上的极,则它们通过单根公共线连接。

Selena认为,每当两条不同的电线相交时,它们就可能相互干扰并造成损坏。所以他想知道有多少对相交?你能帮他解决这个问题吗?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 极数。

以下 $$$n$$$ 行均包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$) — 极点坐标。

保证所有这些 $$$n$$$ 点都是不同的。

输出

打印一个整数——相交的电线对的数量。

示例

输入 #1

4
0 0
1 1
0 3
1 2

输出 #1

14

输入 #2

4
0 0
0 2
0 4
2 0

输出 #2

6

输入 #3

3
-1 -1
1 0
3 1

输出 #3

0

注意

在第一个示例中:

在第二个示例中:

请注意,三个极 $$$(0, 0)$$$、$$$(0, 2)$$$ 和 $$$(0, 4)$$$ 通过单线连接。

在第三个示例中: