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

Автор Qary., 14 лет назад, По-русски
Задача:
Найти точку, равноудаленную от данных отрезков.
(отрезки задаются как float-координаты концов, число отрезков не превосходит 10^6).

Буду благодарен за идею.
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне кажется что у трех отрезков если существует такая точка то одна(при условии что отрезки не вырождены и не совпадают друг с другом ). Так что, наверное, нужно найти такую точку у трех отрезков. А искать наверное таким образом. Точек, равноудаленных от двух отрезков-много, это будет отрезок. Найди этот отрезок, потом добавь еще один из списка и получешь точку, а потом просто подобавляй все отрезки которые еще не проверены. Как-то так.  
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Геом. место точек, равноудаленных от отрезка - прямая, но не отрезок. Не получится.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Все хуже.... отрезок и два луча... 
    • 14 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Нет это к сожалению даже не совсем так. Хуже. Прямая не всегда получается. Надо думать.
      Ты никакое условие не потерял случайно?

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

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Такая мысль появилась. Можно попробовать выйти в 3д, где третье измерение это расстояние до отрезка. Т.е. при z=0 это просто наша плоскость, при z=1 это множество всех точек удаленных от какого-либо отрезка на 1 и т.д. Тогда наши отрезки превратятся в такие разрезаные конуса с двумя плоскими стенками. И можно взять эти фигуры да попересекать. 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    И как это "моделировать" за 2-3 секунды?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не придумал пока как это доказать, но, очень похоже что при последовательном пересечении таких шатров количество сущностей сильно плодиться не будет и трудоемкость в итоге будет линейной.
      • 14 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится


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

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

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

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

        1) точки

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

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

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Проблема в том что непонятно сколько она порождать будет.
          • 14 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
            Ну, по-моему, как ни крути а больше четырех из одной не выйдет. 
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Из одной за один раз-да. А на втором шаге? Третьем?
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                На втором шаге из четырех выйдет максимум 16. А из 16 ничего не выйдет ибо это точки, т.к. размножение идет с понижением размерности.
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          deleted
14 лет назад, # |
Rev. 8   Проголосовать: нравится +1 Проголосовать: не нравится
Утверждение: множество ГМТ равноудаленных от 3 отрезков, у которых ни одна пара отрезков не пересекается, не более чем конечно.
Доказательство: Рассмотрим сначала самый общий случай, когда отрезки не параллельны и не перпендикулярны друг с другом. Как уже было сказано выше, ГМ этих точек-это параболы, отрезки и лучи. Рассмотрим пересечение ГМТ первого и второго отрезка и ГМТ второго и третьего(в дальнейшем пересечение). Это будет пересечение парабол с прямыми, прямых с прямыми(ну или отрезками, лучами-неважно в данном случае), парабол с параболами. Рассмотрим пересечение прямых с прямыми. Так как первый, второй и третий отрезки не лежат на одной прямой, их пересечение даст не более чем конечное число точек. Пересечение параболы и прямой нам так же даст не более чем конечное число точек(это очевидно).
Рассмотрим теперь пересечение двух парабол. Если они пересекаются, то они имеют разный вид, иначе они бы были ГМТ двух одинаковых отрезков с третьим. Иными словами, количество точек пересечения двух ГМТ опять-таки конечно.
Рассмотрим случай когда два отрезка лежат на одной прямой. В этом случае ГМТ этой пары отрезков будет прямая, а ГМТ пары других отрезков(опять пересечение парабол и прямых с прямой) не более чем конечно.
Рассмотрим когда два отрезка из трех перпендикулярны друг другу. Тогда ГМТ этих двух отрезков-опять-таки прямая. И опять получаем конечное количество точек


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



UPD: Случай когда отрезки совпадают своими концами или же пересекаются по отрезку еще не придуман. Случай, когда отрезки просто пересекаются, или же конец одного лежит на другом отрезке, входит в общий случай, т.к. в этом случае только для одной(именно для этой) точки эта точка будет наиближайшей от обоих отрезков.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, еще забыл добавить. Из двух отрезков которые по отрезку пересекаются делай именно пересечение новым отрезком.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так... и где я наложал?
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Наложал я в том что совместились лучи. Значит идея о том что они не совместятся если разный угол была неправильной.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ладно... Тогда ловим блох. Могут ли они совместиться если у нас отрезки не оканчиваются в одной точке?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вот надо понять когда лучи совмещаются

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          UPD: выяснилось что это сектор. Суть не изменилась-как учитывать возможность того что образуется сектор?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Все оказалось еще хуже, чем параболы с отрезками =)

        Там целый сектор в гмт.

        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Нет не сектор. Просто лучи совпали. ГМТ от двух отрезков совершенно точно не должен давать бесконечное количество точек с одинаковым х в случае непересекающихся по отрезку отрезков ибо есть зависимость х от у
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ну как же не сектор, если два отрезка вот так /\

            В верхнем секторе от любой точки кратчайшее расстояние до каждого отрезка это расстояние до общей точки.

            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ай блин это да.... Да, основательно фигово.
              Тогда вообще непонятно как решать эту задачу:) Идеи где после какого-то количества шагов остается конечное число точек пока резко валятся.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Рассмотрен случай когда отрезки просто пересекаются, без пересечения по отрезку или совпадению концов. Рассмотрен выше.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    не более чем конечно

    очень радует этот оборот) как будто бывает менее чем конечно)
    • 14 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится -6 Проголосовать: не нравится
      Может быть более чем конечно.
      Это обычный термин из матана. Это означает что множество не является счетным или имеет размерность континуума. Счетное и континуум предполагают бесконечное число решений
      • 14 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        Во-первых, если множество более чем конечно, то оно вовсе не обязательно счётно или континуально. Например, множество всех подмножеств действительных чисел не счётно и не континуально.

        Во-вторых, я имел в виду совсем другое: оборот не более чем конечно имеет в точности тот же смысл, что и просто конечно.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Прости, просто в этот день был матан, вот я и стал языком матана выражаться:). И я не спорю, что может быть не континуально.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Немного оффтопа на эту тему:
          Меня всегда забавлял термин "общество с ограниченной ответственностью". Неужели все-таки бывают с неограниченной?
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Может я что-то подзабыл, но мне всегда казалось что такой оборот применяют для НБЧС - не более чем счетных. А конечные называют просто конечными =)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну, мой препод иногда и для конечных говорит не более чем
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а если бинпоиск по расстоянию от "всех отрезков" ? 
В начале отсекли все тривиальные случаи ...
допустим предполагаем, что текущее расстояние от все отрезков будет равно h, все отрезки образуют фигуры, напоминающие эллипсы(само собой не эллипсы при этом). Фиксируешь первую такую фигуру, находишь координаты всех пересечений с второй фигурой(тут ангем тебе в помощь- я сам нуб в этом) ... и смотришь, если пересечений вообще нет каком-то шаге, то это расстояние нам не подходит и надо увеличить h... Если пересечения есть, но нет такой точки( одной из пересечений первых двух фигур) в которой каждый последующий отрезок после второго "оставил свое пересечение" с первой фигурой, то надо уменьшить размер h, а если вдруг выяснилось что такая точка есть - мы нашли ответ ... 
думал быстро не факт, что прав.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К сожаленью, тут нет монотонности. Если мы не нашли пересечений при заданном h, то оно может быть как при меньшем так и при большем. Например, если я ничего не напутал, то для трех отрезков, образующих равносторонний треугольник искомая точка только одна - в центре. Если мы промахнемся мимо, то не знаем вниз идти или вверх.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Слишком сложные фигуры образуются.
    Притом, это h порядка 10^(-6), и это явно TL.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да согласен ...
я не учитывал пересечения или смежность отрезков ...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    они могут и не пересечься. Тот же равносторонний треугольник, но теперь обрежь углы. Получается то же самое: точка одна, но ее не найдем.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Для определенности и упрощения, пусть отрезки не пересекаются.
Тогда остаются только прямые. С ними что делать?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Если не пересекаются то похоже мой алгоритм не врет
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • 14 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Может быть еще и луч. Смотри выше.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            0 0 20 0
            0 1 20 0
            0 2 20 0
            три отрезка пересекаются в одной точке, и все точки , ну например, в треугольнике:
            (20,0),(40,0),(40,-2) имеют ближайшей точкой точку (20,0)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А для трех отрезков, которые лежат на одной прямой, это вообще может быть плоскостью в случае если они пересекаются по отрезку.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Да действительно. Мои суждения верны только для конкретной зафиксированой величены d.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Странно, на втором туре областной олимпиады четвертая задача была очень похожа (найти точку, максимум из расстояний от которой до каждой из n заданных прямых минимален)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет, Саш, это разные задачи. Здесь расстояние может быть отнюдь не минимальным.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я не спорю, что они разные. Просто мне кажется что они достаточно схожи. Не в плане решения - в плане условия