Прямі#66

Прямі (Розбір)

Трійка лежить на спільній вертикальній прямій, коли в усіх трьох точок однакова координата , і на спільній горизонтальній — коли однакова координата . Діагоналі, як прямо сказано в умові, не рахуються.

Ці два випадки не перетинаються: якби трійка мала і спільний , і спільний , то всі три точки збіглися б, а за умовою точки різні. Тому відповіді можна просто додати.

Згрупуємо точки за координатою . Якщо в якійсь вертикалі рівно точок, то трійок у ній рівно

\binom{c}{3} = \frac{c(c-1)(c-2)}{6}.

Просумуємо це по всіх вертикалях, потім так само по всіх горизонталях (групуючи за ) і додамо результати.

Для групування зручно взяти словник або масив-лічильник — координати не перевищують , тому вистачить двох масивів довжини .

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