Мэры

Во Флатландии имеется N городов, расположенных на плоскости в точках с координатами (xi, yi). Недавно президент Флатландии решил назначить в каждом городе мэра. При этом, чтобы его нельзя было уличить в дискриминации, он решил назначить на эти посты как мужчин, так и женщин. Для каждой горизонтальной и вертикальной прямой назовем несправедливостью модуль разности между количеством городов на этой прямой, в которых на пост мэра назначены мужчины и количеством городов на этой прямой, в которых на этот пост назначены женщины.
Чтобы показать свою беспристрастность, президент хочет минимизировать суммарную несправедливость по всем вертикальным и горизонтальным прямым. Для каждого города надо определить кого назначить мэром мужчину или женщину. Координаты всех городов целые и N <= 20000