Интересные пары

[wpoms.]

На координатной плоскости даны точки $A_1, A_2 , \ldots, A_n$ с целыми координатами, никакие три из которых не лежат на одной прямой. Пару $(A_i, A_j)$ назовем интересной, если обе координаты середины отрезка $A_iA_j$ являются целыми числами. Найдите наименьшее возможное количество интересных пар.

@темы: Комбинаторика

Comments

[All_ex]

Понятно, что надо множество точек разбить на четыре части, в которых координаты отличаются по чётности... и в каждой вычислить число пар точек...
Интуитивно понятно, что минимум будет, если в каждой паре множеств количество точек отличается не более чем на 1...
Непонятно как это кратко можно записать ... без перебора...