На плоскости расположено несколько отрезков с длинами не превосходящими 1. Всегда ли можно параллельными переносами собрать из них ломаную, расстояние между концами которой было бы меньше 1.5?
Брать отрезки в каком-то порядке - плохая идея. Я начинал с такой же и тоже с 4-х вариантов - потому и застрял.
Пример "неберучка" - два перпендикулярных единичных - строится только диагоняль = корень из 2, и тут "вдруг" берётся ещё один третий - перпендикулярной этой диагоняли - и всё.
Можно отмотать назад и перестроить из первых другую диагональ - тогда оно уже параллельно станет и всё получится - но сложно это и... не правильно что ли.
Словом - не стоит привязывать себя к "порядку", тем более что условие об этом и не просило :)
В таком упрощенном виде - не будет. Между конусами останется зазор, в который можно впихнуть четвертый несократимый отрезок. Тогда надо проверять точное пересечение шаров, а это будет гораздо сложнее - не уверен вот так на глаз, что там получится.
Надо посмотреть будет ли Ваш метод работать для пространства и корня из трех. (Думаю что будет!)
Я имел ввиду, что мы выбираем отрезки один за одним, и достраиваем к нашей ломанной. У ломанной два конца, присоединяем или к одному или к другому. И у отрезка два конца. Присоединяем или одним или другим. Вот мои 4 варианта. По идеи, должно хватить чтобы поддерживать проэкции концов ломанной в рамках 1 по каждой координате.
R-2, а Вы о чем? Откуда 4 варианта, зачем отражения?
Смотрите. Рисуем простенький "циферблат". Берем из кучи любой отрезок и совмещаем с ним циферблат так, чтобы один конец отрезка был в центре циферблата, а второй - где-то на главной оси (зеленой стрелочке). Теперь берем опять же любой второй отрезок и перемещаем его одним концом в центр циферблата. Если второй отрезок попадает в сплошной зеленый сектор - он сокращается с первым (дает в результате снова "подходящий" отрезок длины не более 1) - кладем новый сокращенный отрезок обратно в кучу вместо взятых двух и начинаем все сначала. Если второй отрезок попадает в пунктирный зеленый сектор - то он опять сокращается с первым, только сперва мы его передвинем *другим* концом в центр и он попадет в сплошной зеленый. :) Если второй отрезок попадает в красный сектор, то мы говорим, что он не сокращается с первым (на самом деле зона сокращения больше указанных зеленых секторов, но нам не надо ни сверхточности, ни сверхоптимизации) - тогда мы оставляем второй отрезок валяться и берем третий. Третий отрезок либо попадает в зеленый сектор и сокращается с первым, либо тоже попадает в красный сектор - но тогда он сокращается со вторым! Возвращаем два отрезка в кучу вместо взятых трех и опять начинаем сначала. В конечном итоге у нас не может остаться больше двух отрезков - последние два либо сократятся, либо останется пара красный-зеленый. Других вариантов нет - откуда 4?
О чем это вы? Задача как раз и есть о способе "сокращения." Который очевиден только для одномерного случая. Отрезки на прямой, и расстояние между концами 1. Для двумерного случая тоже вроде получантся. Я бы сказал что строя ломанную из двух отрезков к нас есть 4 варианта. А нам надо научиться "отражать" относитально оси X и Y, т.е. тоже 4 варианта. Но вот что делать в пространстве - не понятно. Хочеться получить расстояние меньше 1.73(1.74) Для этого надо поддерживать три координаты в рамках 0-1. А вариантов склеивания 2 отрезков по-прежнему 2 :-(
ivana2000: По условиям все отрезки расположены в одной плоскости.
Пояснение.
Собираемая ломаная может быть замкнутой, может самопересекаться, в том числе и в вершинах, может быть вырожденной, если есть параллельные отрезки.
Ладно, возьмем некрасивый пример, чисто для иллюстрации.
Два идентичных единичных отрезка - их придется либо совместить, получив "туда и обратно", что и ломаной-то назвать не у каждого язык повернется :))) а уж самопересечений там будет завались; либо построить из них один большой отрезок длины 2, который является вырожденной ломаной без самопересечений, но никак не впишется в меньше 1.5 между концами.
Ну - умалчивает значит таки не запрещает, хоя.... что-то я тут уже третий рисунок набрасываю - и всё только хуже и хуже становится. А для три по 45 - если так?
(частные-то случАи как-то все сходядся - обобщить никак не выходит, не пойму с какой стороны взяться лучше)
:) K2, тут Вы неправы. "Всегда" и "из любого набора отрезокв, удовлетворяющих условию" - это не совсем одно и тоже. Даже совсем не одно и то же.
Скажем, *когда* Вам захочется собрать ломаную без самопересечений (а условие на этот счет скромно отмалчивается) - то это Вам очевидно не удастся даже в простом случае, - три единичных отрезка с шагом наклона в 45 градусов, например.