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

Автор mdldml, 15 лет назад, По-русски

Я тоже выложу задачу=)

Дома четырех дачников расположены в совершенно необустроенной местности в вершинах квадрата со стороной 1000 м. У них хватает строительного материала только на 2800 м дорог, могут ли они построить такую систему дорог, чтобы от любой дачи можно было добраться до любой другой? Если да, приведите пример, если нет, то докажите невозможность.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да вроде можно. строим дерево Штейнера, сумма длин дорог вроде меньше 2800
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    эх... писал за 5 минут до начала соревнования, пример не вставил. впрочем, ниже его уже привели.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Желательно привести пример)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По-моему, решение тривиально - провести диагонали. 2 * 1000 *  / sqrt{2} / approx2800