这是问题的困难版本。与简单版本的唯一区别是,在此版本中,坐标可以是奇数也可以是偶数。
在平面上的不同坐标处有 $$$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$$$ 的奶牛。