Точки на плоскости
*
Опубликовано:
02.01.2012
Категория:
Сложность:
На плоскости дано 2n точек. Докажите, что их можно попарно соединить так, чтобы отрезки не пересекались.
Подсказка
В выпуклом четырёхугольнике сумма длин диагоналей всегда больше суммы длин двух противоположных сторон.
Решение
Рассмотрим все возможные варианты соединения точек n отрезками и выберем из них тот, для которого сумма длин отрезков минимальна. Если в нём какие-то два отрезка AB и CD пересекаются, то, заменив их на пару AC, BD, получим набор отрезков меньшей длины, что противоречит выбору минимального набора.
Добавить комментарий