Это было проблемой на конкурсе Pacific ACM-ICPC в 2010 году. Суть его заключается в том, чтобы найти способ разбивать множество точек внутри треугольника на три подтреугольника, так что каждый раздел содержит ровно треть точек.
Ввод:
- Координаты ограничивающего треугольника:
(v1x,v1y),(v2x,v2y),(v3x,v3y)
- Число
3n < 30000
, представляющее число точек, лежащих внутри треугольника - Координаты точек
3n
:(x_i,y_i)
дляi=1...3n
Вывод:
- Точка
(sx,sy)
, которая разбивает треугольник на 3 подтреугольника, так что каждый поддиапазон содержит ровноn
точек.
То, как точка расщепления разбивает ограничивающий треугольник на субтреугольники, выглядит следующим образом: Нарисуйте линию от точки расщепления до каждой из трех вершин. Это разделит треугольник на 3 подтреугольника.
Нам гарантируется, что такая точка существует. Любая такая точка будет достаточной (ответ не обязательно уникален).
Вот пример проблемы для n=2
(6 баллов). Нам даны координаты каждой из цветных точек и координат каждой вершины большого треугольника. Точка разделения окружена серым цветом.
Может ли кто-нибудь предложить алгоритм быстрее, чем O(n^2)
?