Блог пользователя Planshetnik

Автор Planshetnik, 13 лет назад, По-русски
Привет всем,
Подскажите пожалуйста как решать задачу:
На плоскость были натыканы (в хаотичном порядке) n раз по четыре точки (за раз), которые (эти четыре точки) если соединить образуют квадрат (и стороны квадрата будут параллельны осям).
Найти многоугольник с минимальной площадью, и чтобы линии краев этого многоугольника были параллельны осям координат.

Есть ли какой алгоритм или нужно придумывать?

з.ы. Если как-то плохо объяснил, то могу нарисовать.
UPD: поправил.
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Именно выпуклую? Тогда это ведь прямоугольник (min_x, min_y) -- (max_x, max_y). И квадраты тут ничем не помогут.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Очень похожая задача с разбором