Задача
На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.
Входные данные
В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].
Выходные данные
Искомое число [latex]k[/latex].
Тесты
Входные данные | Выходные данные |
---|---|
5 2 -1 3 0 0 4 -3 0 -2 1 |
6 |
5 0 0 2 4 6 6 10 34 -42 -48 |
10 |
4 0 0 0 1 1 0 1 1 |
0 |
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2 |
24 |
5 0 0 0 1 -1 0 -1 -1 3 -3 |
3 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; int main() { unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0}; unsigned long long c = 0; cin >> n; for (int i = 0; i < n; i ++){ cin >> x1 >> y1; if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++; else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++; else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++; else A [3] ++; } for(int i = 0; i < 4; i ++){ for(int j= 0; j < 4; j ++){ if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6; else c += A[i] * (A[i] - 1) * A[j] / 2; } } cout << c; return 0; } |
Решение задачи
Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.
Ссылки
Условие задачи на сайте E-Olymp
код задачи на Ideone
описание теоремы Пика на Wikipedia
описание псевдоскалярного произведения на Wikipedia