Трійка лежить на спільній вертикальній прямій, коли в усіх трьох точок однакова координата , і на спільній горизонтальній — коли однакова координата . Діагоналі, як прямо сказано в умові, не рахуються.
Ці два випадки не перетинаються: якби трійка мала і спільний , і спільний , то всі три точки збіглися б, а за умовою точки різні. Тому відповіді можна просто додати.
Згрупуємо точки за координатою . Якщо в якійсь вертикалі рівно точок, то трійок у ній рівно
Просумуємо це по всіх вертикалях, потім так само по всіх горизонталях (групуючи за ) і додамо результати.
Для групування зручно взяти словник або масив-лічильник — координати не перевищують , тому вистачить двох масивів довжини .
Складність — \mathcal{O}(n + C), де — діапазон координат. При n \le 100 можна було б обійтися й потрійним перебором за \mathcal{O}(n^3), але підхід через комбінації працює й для значно більших .