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

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

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

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

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

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