← 返回题目列表

Codeforces · 1548/D2

D2. 格雷戈尔和奇怪的奶牛(困难)

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

这是问题的困难版本。与简单版本的唯一区别是,在此版本中,坐标可以是奇数也可以是偶数。

在平面上的不同坐标处有 $$$n$$$ 栅栏柱。确保没有三个栅栏柱位于同一条线上。

平面上有无数头牛,每个点都有一头,坐标为整数。

Gregor 是光明会的成员,想要建造一个三角形栅栏,连接 $$$3$$$ 不同的现有栅栏柱。据说,一头牛被严格限制在栅栏内。如果围起来的牛的数量是奇数,并且栅栏的面积是整​​数,则称栅栏是有趣的。

找出感兴趣的栅栏的数量。

输入

第一行包含整数 $$$n$$$ ($$$3 \le n \le 6000$$$),Gregor 可以选择形成栅栏顶点的栅栏柱数。

接下来的 $$$n$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x,y \le 10^7$$$,其中 $$$(x,y)$$$ 是栅栏柱的坐标。所有栅栏柱位于不同的坐标处。没有三个栅栏柱位于同一行。

输出

打印一个整数,即感兴趣的栅栏的数量。如果两个栅栏由不同的三个栅栏柱组成,则它们被视为不同。

示例

输入 #1

3
0 0
2 0
0 4

输出 #1

1

输入 #2

4
1 8
0 6
5 2
5 6

输出 #2

1

输入 #3

10
170 59
129 54
5 98
129 37
58 193
154 58
24 3
13 138
136 144
174 150

输出 #3

29

注意

在第一个示例中,只有 $$$1$$$ 栅栏。那个栅栏很有趣,因为它的面积是 $$$4$$$,并且有 $$$1$$$ 封闭的牛,用红色标记。

在第二个示例中,有 $$$4$$$ 可能的栅栏。然而,只有其中之一是有趣的。该栅栏面积为 $$$8$$$,围着 $$$5$$$ 的奶牛。