Любителям алгоритмов

Discussion in 'Болталка' started by Onths, 3 Jul 2013.

  1. Onths

    Onths New Member

    Joined:
    3 May 2012
    Messages:
    57
    Likes Received:
    2
    Reputations:
    -4
    Забавные задачи, алгоритмика плюс легкая геометрия.
    Не нужно ничего конкретного, достаточно попросту описать вашу идею/подход.

    1. Дана обыкновенная плоскость. Вводятся точки: координаты x,y. Найти, если возможно, путем объедения введенных точек, три равносторонних треугольника с наименьшей площадью.

    2. Число - номер комнаты. Задаются пары чисел - ходы между комнатами.
    В конце нужно найти путь из одной комнаты в другую.
     
    #1 Onths, 3 Jul 2013
    Last edited: 3 Jul 2013
  2. trolex

    trolex Well-Known Member

    Joined:
    6 Dec 2009
    Messages:
    597
    Likes Received:
    1,391
    Reputations:
    6
    в голову приходит только брут
    1. N точек, считаем расстояние от каждой до каждой, получаем таблицу N на N, ищем одинаковые расстояния, если их меньше 3 отбрасываем, три вычисляем площадь треугольника, больше трёх - вычисляем площади всех треугольников которые можно составить из этих точек,
    потом среди всех площадей ищем 3 минимальных
    2. двунаправленный поиск, берём начальную комнату перебираем пары смотрим куда можем попасть, если нет конечной, то для каждой найденой комнаты смотрим куда можем попасть, для ускорения можно сразу и от начала и от конца искать и ждать пока пути сойдутся в какой либо комнате

    можно как то оптимизировать?
     
  3. Hunter.1121

    Hunter.1121 Elder - Старейшина

    Joined:
    23 Oct 2005
    Messages:
    143
    Likes Received:
    30
    Reputations:
    17
    можно конечно, например для первой задачи дополнительное условие - треугольники равностороннме. Т.е. берем все возможные пары точек (это будет одна из сторон) и принимая любую из точек пары за центр окружности с радиусом, равным расстоянию между этими двумя точками ищем точки с координатами, удовлетворяющими уравнению окружности с соответствующим центром. Если такие находятся, то проверяем расстояние между найденой точкой и второй точкой (не забыть исключить из перебора эту вторую точку) - если расстояние равно расстоянию между парой исходных точек, то найден равносторонний треугольник. Сохраняем координаты точек и площадь треугольника. Потом просто ищем наименьшие из сохраненных площадей и выдаем соответствующие им координаты точек.
    По второй задаче по поводу оптимизации думать надо)
     
Loading...