Это сложная версия задачи. Единственное отличие от простой версии заключается в том, что в данной версии координаты могут быть как чётными, так и нечётными.
Даны \(n\) столбов, расположенных в различных точках на плоскости. Гарантируется, что никакие три столба не лежат на одной прямой.
На плоскости также есть бесконечное количество коров, по одной в каждой точке с целочисленными координатами.
Грегор — член общества иллюминатов и хочет построить треугольный загон, соединив \(3\) различных существующих столба забором. Корова, находящаяся строго внутри загона, считается огражденной. Если ограждено нечётное число коров, и при этом площадь загона равна целому числу, то загон считается интересным.
Найдите количество интересных загонов.
Выходные данные
Напечатайте одно целое число — количество интересных загонов. Два загона считаются различными, если они образованы различными множествами трех столбов.
Примечание
В первом примере существует только \(1\) загон. Этот загон является интересным, поскольку его площадь равна \(4\) и есть \(1\) пойманная корова, помеченная красным.
Во втором примере существует \(4\) возможных загона. Однако, только один из них является интересным. Этот загон имеет площадь, равную \(8\), и \(5\) пойманных коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0
2 0
0 4
|
1
|
|
2
|
4
1 8
0 6
5 2
5 6
|
1
|
|
3
|
10
170 59
129 54
5 98
129 37
58 193
154 58
24 3
13 138
136 144
174 150
|
29
|