Задача:
Найти точку, равноудаленную от данных отрезков.
(отрезки задаются как float-координаты концов, число отрезков не превосходит 10^6).
Буду благодарен за идею.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 144 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Если б луча... там тоже будет такая фигня с параболами =(
На пальцах примерно так получается...
Текущее пересечение может состоять из фигур трех размерностей.
3) полоса или сектор конуса
2) куски прямой или параболы
1) точки
Дальше, конечно, очень много вариантов, но вроде как получается что при пересечении с очередным шатром каждая фигура может ЛИБО остаться фигурой той же размерности ЛИБО породить несколько фигур меньшей размерности. Но не может сделать и то и то. Таким образом, общее число фигур на каждом шаге не будет превышать некоторой константы. Навскидку констату можно оценить в 4*4*4, но, думаю что есть и более сильная оценка.
UPD: похоже, в 2 не только прямые и параболы, а еще и остальной зоопарк с эллипсами и гиперболами. Но суть та же.
>>>множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается по отрезку, не более чем конечно.
враки - три отрезка с общим концом и небольшим углом между ними.
Все оказалось еще хуже, чем параболы с отрезками =)
Там целый сектор в гмт.
Ну как же не сектор, если два отрезка вот так /\
В верхнем секторе от любой точки кратчайшее расстояние до каждого отрезка это расстояние до общей точки.
Меня всегда забавлял термин "общество с ограниченной ответственностью". Неужели все-таки бывают с неограниченной?
Моя идея такая: для 3 несовпадающих отрезков решение представляет собой либо точку, либо отрезок в котором расстояние от всех точек до наших отрезков одинаково. попробуем найти такую область. (Было бы хорошо это проверить)
Зафиксируем 3 отрезка. Будем делать бинпоиск по расстоянию (d) от отрезков. Для каждого из 3 отрезков закрасим, область из точек расстояние от которых до отрезка <= d. Пересечем 3 такие области (множество точек этой области кстати будет выпуклым). Утверждается что наша искомая точка лежит в пересечении этих 3 областей. Действительно, если точка равноудаленная от всех отрезков существует и ее расстояние до всех отрезков (D) D <= d, то она будет включена в заштрихованную область каждого отрезка, а следовательно и в их пересечение. В линейной алгебре есть теорема говорящая, что пересечение выпуклых множеств есть выпуклое множество. Возможно это тут как то поможет.
После нахождения такой точки, можно просчитать расстояния от нее до всех остальных отрезков и сказать одинаковы ли они или нет. Если же у нас отрезок, то его можно попересекать с уже не закрашенными областями равноудаленных точек от i-ого отрезка и получить таким образом либо отрезок либо точку.
О я придумал как доказать что это отрезок или точка. Можно бинпоиск проводить до тех пор, пока область пересечения не станет маленькой и тогда ее можно считать равной 0.
1) Область пересечения будет выпуклой и, следовательно, связной.
2) Наша область пересечения будет вырождаться в какую-то линию.
3) Выпуклая линия -- есть прямая, или ее часть (Например, луч, отрезок или точка, как в нашем случае).
Так как наша линия ограничена закрашеными областями вокруг отрезков, то она не может быть лучем или прямой. Следовательно наша область -- отрезок или точка.
>>>множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается по отрезку, не более чем конечно.
враки - три отрезка с общим концом и небольшим углом между ними.
>>> враки - три отрезка с общим концом и небольшим углом между ними.
Я не смог подобрать пример. Можешь его дат ьмне с координатах, пожалуйста.
>>>для 3 несовпадающих отрезков решение представляет собой либо точку, либо отрезок в котором расстояние от всех точек до наших отрезков одинаково.
Для непересекающихся, кажется, верно, а для просто несовпадающих выше уже был пример с тремя отрезками у которых один конец общий и угол между ними небольшой. Тогда там целый сектор подходит.