这个问题和上一个问题一样,但是有更大的约束。
那是一个周日的早晨,三个朋友 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)$$$ 通过单线连接。
在第三个示例中: