Я обнаружил эту проблему на соревнованиях по программированию в Венгрии для учеников старших классов. Я не смог ее решить, но потом не смог найти решение - ни у кого из меня не было рабочей идеи.
Проблема (в двух словах):
Учитывая набор из N точек , определите, существует ли выпуклый квад из этих точек (углы четырехугольников взяты из набора точек), внутри которого нет другой точки содержится (нет пятой точки, которая находится внутри или на краю четырехугольника).
Если такой квадрат существует, верните точки (индекс точек на входе) в (любом) порядке против часовой стрелки.
Если такого квадрата не существует, вернуть 0 0 0 0.
Пределы:
Вы получаете 1<=K<=10 наборов с 1<=N[i]<=100 000 точками с координатами -1 000 000 <=x,y<=1 000 000
Ограничение времени: 0,2 сек
Ограничение памяти: 32 МБ
Наивный раствор:
For every subset with four points (N(N-1)(N-2)(N-3)/24):
Check if resulting quad is convex! If no, continue to next subset.
For every other (N-4) points:
Check if it is contained in the quad
If no point is contained, return the quad.
If no quad was returned, return "0 0 0 0"
Сложность времени: O(n^5)!
Другая идея (не думаю, что это поможет):
Сделайте триангуляцию набора точек, затем проверьте только соседние треугольники. Проблема в том, что существует множество возможных триангуляций для набора точек ( см. ), и мы можем упустить правильное решение.
Если кто-то может доказать, что триангуляция, которая (максимизирует угол или минимизирует площадь или что-то в этом роде) всегда дает решение, это может сработать.