Какая-то геометрия..

14 лет назад, # |

Мне кажется что у трех отрезков если существует такая точка то одна(при условии что отрезки не вырождены и не совпадают друг с другом ). Так что, наверное, нужно найти такую точку у трех отрезков. А искать наверное таким образом. Точек, равноудаленных от двух отрезков-много, это будет отрезок. Найди этот отрезок, потом добавь еще один из списка и получешь точку, а потом просто подобавляй все отрезки которые еще не проверены. Как-то так.

→ Ответить

14 лет назад, # ^ |

Геом. место точек, равноудаленных от отрезка - прямая, но не отрезок. Не получится.

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

Все хуже.... отрезок и два луча...

→ Ответить

14 лет назад, # ^ |

-8

Нет это к сожалению даже не совсем так. Хуже. Прямая не всегда получается. Надо думать.

Ты никакое условие не потерял случайно?

→ Ответить

-dp-	14 лет назад, # ^ \| ← Rev. 3 → 0 Что-то мне кажется что гмт точек равноудаленных от двух отрезков это в общем случае что-то страшное типа отрезка и двух лучей, соединенных кусками параболы. → Ответить

14 лет назад, # ^ |

-8

Я уже понял что не отрезок, но откуда парабола? о_0

→ Ответить

14 лет назад, # ^ |

-8

А, понял.

→ Ответить

natalia

14 лет назад, # ^ |

Отрезки могут пересекаться, тогда будет 4 луча

→ Ответить

-dp-	14 лет назад, # ^ \| 0 Если б луча... там тоже будет такая фигня с параболами =( → Ответить

14 лет назад, # |

Нет, условия я не терял.

→ Ответить

14 лет назад, # |

Такая мысль появилась. Можно попробовать выйти в 3д, где третье измерение это расстояние до отрезка. Т.е. при z=0 это просто наша плоскость, при z=1 это множество всех точек удаленных от какого-либо отрезка на 1 и т.д. Тогда наши отрезки превратятся в такие разрезаные конуса с двумя плоскими стенками. И можно взять эти фигуры да попересекать.

→ Ответить

14 лет назад, # ^ |

И как это "моделировать" за 2-3 секунды?

→ Ответить

-dp-	14 лет назад, # ^ \| 0 Не придумал пока как это доказать, но, очень похоже что при последовательном пересечении таких шатров количество сущностей сильно плодиться не будет и трудоемкость в итоге будет линейной. → Ответить

14 лет назад, # ^ |

← Rev. 4 →

На пальцах примерно так получается...

Текущее пересечение может состоять из фигур трех размерностей.

3) полоса или сектор конуса

2) куски прямой или параболы

1) точки

Дальше, конечно, очень много вариантов, но вроде как получается что при пересечении с очередным шатром каждая фигура может ЛИБО остаться фигурой той же размерности ЛИБО породить несколько фигур меньшей размерности. Но не может сделать и то и то. Таким образом, общее число фигур на каждом шаге не будет превышать некоторой константы. Навскидку констату можно оценить в 4*4*4, но, думаю что есть и более сильная оценка.

UPD: похоже, в 2 не только прямые и параболы, а еще и остальной зоопарк с эллипсами и гиперболами. Но суть та же.

→ Ответить

14 лет назад, # ^ |

Проблема в том что непонятно сколько она порождать будет.

→ Ответить

-dp-	14 лет назад, # ^ \| ← Rev. 3 → 0 Ну, по-моему, как ни крути а больше четырех из одной не выйдет. → Ответить

14 лет назад, # ^ |

Из одной за один раз-да. А на втором шаге? Третьем?

→ Ответить

-dp-	14 лет назад, # ^ \| 0 На втором шаге из четырех выйдет максимум 16. А из 16 ничего не выйдет ибо это точки, т.к. размножение идет с понижением размерности. → Ответить

14 лет назад, # ^ |

А кажется понял.

→ Ответить

-dp-	14 лет назад, # ^ \| ← Rev. 2 → 0 deleted → Ответить

14 лет назад, # |

← Rev. 8 →

Утверждение: множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается, не более чем конечно.

Доказательство: Рассмотрим сначала самый общий случай, когда отрезки не параллельны и не перпендикулярны друг с другом. Как уже было сказано выше, ГМ этих точек-это параболы, отрезки и лучи. Рассмотрим пересечение ГМТ первого и второго отрезка и ГМТ второго и третьего(в дальнейшем пересечение). Это будет пересечение парабол с прямыми, прямых с прямыми(ну или отрезками, лучами-неважно в данном случае), парабол с параболами. Рассмотрим пересечение прямых с прямыми. Так как первый, второй и третий отрезки не лежат на одной прямой, их пересечение даст не более чем конечное число точек. Пересечение параболы и прямой нам так же даст не более чем конечное число точек(это очевидно).

Рассмотрим теперь пересечение двух парабол. Если они пересекаются, то они имеют разный вид, иначе они бы были ГМТ двух одинаковых отрезков с третьим. Иными словами, количество точек пересечения двух ГМТ опять-таки конечно.

Рассмотрим случай когда два отрезка лежат на одной прямой. В этом случае ГМТ этой пары отрезков будет прямая, а ГМТ пары других отрезков(опять пересечение парабол и прямых с прямой) не более чем конечно.

Рассмотрим когда два отрезка из трех перпендикулярны друг другу. Тогда ГМТ этих двух отрезков-опять-таки прямая. И опять получаем конечное количество точек

Ко всему остается добавить что количество точек будет небольшим. Я думаю в ТЛ войдет если ты после трех отрезков будешь просто каждую точку проверять.

UPD: Случай когда отрезки совпадают своими концами или же пересекаются по отрезку еще не придуман. Случай, когда отрезки просто пересекаются, или же конец одного лежит на другом отрезке, входит в общий случай, т.к. в этом случае только для одной(именно для этой) точки эта точка будет наиближайшей от обоих отрезков.

→ Ответить

14 лет назад, # ^ |

Да, еще забыл добавить. Из двух отрезков которые по отрезку пересекаются делай именно пересечение новым отрезком.

→ Ответить

-dp-	14 лет назад, # ^ \| 0 >>>множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается по отрезку, не более чем конечно. враки - три отрезка с общим концом и небольшим углом между ними. → Ответить

14 лет назад, # ^ |

Так... и где я наложал?

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Наложал я в том что совместились лучи. Значит идея о том что они не совместятся если разный угол была неправильной.

→ Ответить

14 лет назад, # ^ |

Ладно... Тогда ловим блох. Могут ли они совместиться если у нас отрезки не оканчиваются в одной точке?

→ Ответить

14 лет назад, # ^ |

Вот надо понять когда лучи совмещаются

→ Ответить

14 лет назад, # ^ |

UPD: выяснилось что это сектор. Суть не изменилась-как учитывать возможность того что образуется сектор?

→ Ответить

-dp-	14 лет назад, # ^ \| 0 Все оказалось еще хуже, чем параболы с отрезками =) Там целый сектор в гмт. → Ответить

14 лет назад, # ^ |

← Rev. 2 →

Нет не сектор. Просто лучи совпали. ГМТ от двух отрезков совершенно точно не должен давать бесконечное количество точек с одинаковым х в случае непересекающихся по отрезку отрезков ибо есть зависимость х от у

→ Ответить

-dp-	14 лет назад, # ^ \| 0 Ну как же не сектор, если два отрезка вот так /\ В верхнем секторе от любой точки кратчайшее расстояние до каждого отрезка это расстояние до общей точки. → Ответить

14 лет назад, # ^ |

Ай блин это да.... Да, основательно фигово.

Тогда вообще непонятно как решать эту задачу:) Идеи где после какого-то количества шагов остается конечное число точек пока резко валятся.

→ Ответить

14 лет назад, # ^ |

Рассмотрен случай когда отрезки просто пересекаются, без пересечения по отрезку или совпадению концов. Рассмотрен выше.

→ Ответить

steiner

14 лет назад, # ^ |

не более чем конечно

очень радует этот оборот) как будто бывает менее чем конечно)

→ Ответить

14 лет назад, # ^ |

← Rev. 5 →

-6

Может быть более чем конечно.

Это обычный термин из матана. Это означает что множество не является счетным или имеет размерность континуума. Счетное и континуум предполагают бесконечное число решений

→ Ответить

steiner

14 лет назад, # ^ |

Во-первых, если множество более чем конечно, то оно вовсе не обязательно счётно или континуально. Например, множество всех подмножеств действительных чисел не счётно и не континуально.

Во-вторых, я имел в виду совсем другое: оборот не более чем конечно имеет в точности тот же смысл, что и просто конечно.

→ Ответить

14 лет назад, # ^ |

Прости, просто в этот день был матан, вот я и стал языком матана выражаться:). И я не спорю, что может быть не континуально.

→ Ответить

dalex

14 лет назад, # ^ |

Немного оффтопа на эту тему:
Меня всегда забавлял термин "общество с ограниченной ответственностью". Неужели все-таки бывают с неограниченной?

→ Ответить

-dp-	14 лет назад, # ^ \| +3 Может я что-то подзабыл, но мне всегда казалось что такой оборот применяют для НБЧС - не более чем счетных. А конечные называют просто конечными =) → Ответить

14 лет назад, # ^ |

Ну, мой препод иногда и для конечных говорит не более чем

→ Ответить

blazerer

14 лет назад, # |

а если бинпоиск по расстоянию от "всех отрезков" ?

В начале отсекли все тривиальные случаи ...

допустим предполагаем, что текущее расстояние от все отрезков будет равно h, все отрезки образуют фигуры, напоминающие эллипсы(само собой не эллипсы при этом). Фиксируешь первую такую фигуру, находишь координаты всех пересечений с второй фигурой(тут ангем тебе в помощь- я сам нуб в этом) ... и смотришь, если пересечений вообще нет каком-то шаге, то это расстояние нам не подходит и надо увеличить h... Если пересечения есть, но нет такой точки( одной из пересечений первых двух фигур) в которой каждый последующий отрезок после второго "оставил свое пересечение" с первой фигурой, то надо уменьшить размер h, а если вдруг выяснилось что такая точка есть - мы нашли ответ ...

думал быстро не факт, что прав.

→ Ответить

14 лет назад, # ^ |

К сожаленью, тут нет монотонности. Если мы не нашли пересечений при заданном h, то оно может быть как при меньшем так и при большем. Например, если я ничего не напутал, то для трех отрезков, образующих равносторонний треугольник искомая точка только одна - в центре. Если мы промахнемся мимо, то не знаем вниз идти или вверх.

→ Ответить

14 лет назад, # ^ |

Слишком сложные фигуры образуются.

Притом, это h порядка 10^(-6), и это явно TL.

→ Ответить

blazerer

14 лет назад, # |

да согласен ...

я не учитывал пересечения или смежность отрезков ...

→ Ответить

14 лет назад, # ^ |

они могут и не пересечься. Тот же равносторонний треугольник, но теперь обрежь углы. Получается то же самое: точка одна, но ее не найдем.

→ Ответить

14 лет назад, # |

Для определенности и упрощения, пусть отрезки не пересекаются.

Тогда остаются только прямые. С ними что делать?

→ Ответить

14 лет назад, # ^ |

Если не пересекаются то похоже мой алгоритм не врет

→ Ответить

14 лет назад, # |

Моя идея такая: для 3 несовпадающих отрезков решение представляет собой либо точку, либо отрезок в котором расстояние от всех точек до наших отрезков одинаково. попробуем найти такую область. (Было бы хорошо это проверить)

Зафиксируем 3 отрезка. Будем делать бинпоиск по расстоянию (d) от отрезков. Для каждого из 3 отрезков закрасим, область из точек расстояние от которых до отрезка <= d. Пересечем 3 такие области (множество точек этой области кстати будет выпуклым). Утверждается что наша искомая точка лежит в пересечении этих 3 областей. Действительно, если точка равноудаленная от всех отрезков существует и ее расстояние до всех отрезков (D) D <= d, то она будет включена в заштрихованную область каждого отрезка, а следовательно и в их пересечение. В линейной алгебре есть теорема говорящая, что пересечение выпуклых множеств есть выпуклое множество. Возможно это тут как то поможет.

После нахождения такой точки, можно просчитать расстояния от нее до всех остальных отрезков и сказать одинаковы ли они или нет. Если же у нас отрезок, то его можно попересекать с уже не закрашенными областями равноудаленных точек от i-ого отрезка и получить таким образом либо отрезок либо точку.

→ Ответить

14 лет назад, # ^ |

← Rev. 6 →

О я придумал как доказать что это отрезок или точка. Можно бинпоиск проводить до тех пор, пока область пересечения не станет маленькой и тогда ее можно считать равной 0.

1) Область пересечения будет выпуклой и, следовательно, связной.

2) Наша область пересечения будет вырождаться в какую-то линию.

3) Выпуклая линия -- есть прямая, или ее часть (Например, луч, отрезок или точка, как в нашем случае).

Так как наша линия ограничена закрашеными областями вокруг отрезков, то она не может быть лучем или прямой. Следовательно наша область -- отрезок или точка.

→ Ответить

14 лет назад, # ^ |

Может быть еще и луч. Смотри выше.

→ Ответить

14 лет назад, # ^ |

>>>множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается по отрезку, не более чем конечно.

враки - три отрезка с общим концом и небольшим углом между ними.

→ Ответить

14 лет назад, # ^ |

>>> враки - три отрезка с общим концом и небольшим углом между ними.

Я не смог подобрать пример. Можешь его дат ьмне с координатах, пожалуйста.

→ Ответить

14 лет назад, # ^ |

0 0 20 0

0 1 20 0

0 2 20 0

три отрезка пересекаются в одной точке, и все точки , ну например, в треугольнике:

(20,0),(40,0),(40,-2) имеют ближайшей точкой точку (20,0)

→ Ответить

14 лет назад, # ^ |

А для трех отрезков, которые лежат на одной прямой, это вообще может быть плоскостью в случае если они пересекаются по отрезку.

→ Ответить

14 лет назад, # ^ |

>>>для 3 несовпадающих отрезков решение представляет собой либо точку, либо отрезок в котором расстояние от всех точек до наших отрезков одинаково.

Для непересекающихся, кажется, верно, а для просто несовпадающих выше уже был пример с тремя отрезками у которых один конец общий и угол между ними небольшой. Тогда там целый сектор подходит.

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Да действительно. Мои суждения верны только для конкретной зафиксированой величены d.

→ Ответить

skaramouche

14 лет назад, # |

Странно, на втором туре областной олимпиады четвертая задача была очень похожа (найти точку, максимум из расстояний от которой до каждой из n заданных прямых минимален)

→ Ответить