Трикутники на площині#12950

Трикутники на площині (Розбір)

Відсортуємо всі точок за зростанням їхніх координат . У випадку рівності координат , відсортуємо за зростанням координат . Таким чином, отримаємо впорядкований список точок: P_1, P_2, \ldots, P_{3n}.

Розділимо відсортований список точок на груп по три сусідні точки:

\{P_1, P_2, P_3\}, \{P_4, P_5, P_6\}, \ldots, \{P_{3n-2}, P_{3n-1}, P_{3n}\}

Для кожної групи з трьох точок побудуємо трикутник. Таким чином, отримаємо трикутників, що задовольняють умову.