И вновь геометрия

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всем доброго времени суток. Ребята, есть задачка: На плоскости задаются 2 множества точек — А и В, |A|=|B|=n. Пусть никакие 3 точки не коллинеарные. Нужно так сформировать пари (a, b), где a — точка из множества А, b — точка из множества B, чтобы никакие 2 отрезки не пересекались. Задача пересечения 2 отрезков всем известная, потому хотелось бы услышать идею именно на счет построения отрезков с такими условиями. Есть тривиальная идея полного перебора (в принципе, здесь бы подошел и бэктрекинг), но хотелось бы узнать, есть ли более оптимальные методы решения. Так же, если на каких-то архивах есть похожие задачки, то хотелось бы узнать их номера. Буду очень благодарен :))).

Комментарии (23)

Показать архивные | Написать комментарий?

riadwaw

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

← Rev. 2 →

А что если соединить сперва как-ннибудь жадно, а потом пока есть пересечения перестраивать очевидным образом? Ясно, что процесс завершится ибо сумма длин каждый раз уменьшается.

Ясно, что работает не быстро, но все же вроде быстрее перебора наверно (По грубым оценкам — отрезков полином, точек пересечения полином => не более полинома раз что-то сделаем за какой-то опять же полином). А если еще соединить как-то хитро(например к каждой точке выбирать ближайшую свободную, или отсортить по 1 из координат и первую сединять с первой), то на практике должно быть быстрее.

→ Ответить

Berezin

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

Могу ошибиться, Но задача напоминает (а может она и есть) Задачу со Всеукра. Либо прошлого, либо позапрошлого. Сводилась к построению выпуклой оболочки. На ней отрезки 100% не пересекаются. Отрезки брались, последовательные. А если две точки, стоящие рядом были из одного множества, соответственно не берем отрезок. Точки, отрезки которых мы взяли удаляем и переходим к шагу 1.

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

PS: по понятным причинам всеукр не писал

А я писал. Это был мой первый Всеукр. Я на ней тогда 25 баллов набрал. И еще на первой задаче (что-то типа найти сумму коэффициентов многочлена) на радостях от придуманного решения неправильно написал цикл вознесения числа в степень по модулю. О быстром тогда еще даже не знал, но навтыкал даже в линейном. Да... есть что вспомнить.

P.S. Через 4 дня еду, как-раз таки, на свой третий, и, увы, последний Всеукр.

Renderhp

Если я не ошибаюсь, то если выпуклая одного цвета, то можно просто взять и провести какую-то мнимую вертикальную (горизонтальную) прямую, разбив точки на две части и рекурсивно решить данную задачу для обеих

А по какому принципу выбирать прямую?

Могу ошибиться, но не всякая прямая гарантирует решение. Так ведь?

Если в обеих частях будет поровну обоих цветов, то гарантирует вполне себе.

Но непонятно, как это сделать, впрочем

Ну пока все точки не обработаны: 1) ищем выпуклую оболочку 1.1) если на ней есть разные точки, то добавляем их (выводим там и т.п) и к п.1 1.2) если нет, то разбиваем пополам по цветам и передаем в рекурсию две части (или много памяти?)

Почему можно разделить пополам?

Ну можно разделить примерно пополам (+-1 точка). Поскольку, нет 3х коллинеарных, то это возможно.

UPD: Хотя даже не очень принципиально, чтоб именно пополам. Главное, чтобы в каждом подмножестве было поровну точек. Опять же то, что нет троих коллинеарных, гарантирует (разве, нет?) то, что такое разбиение есть..

Если пытаться проводить только в 1 направлении — то нет

Пример(вертикальной тут нет, да и гориз. вроде тоже)

a               a
     b
    b  b
 a          a        
    b  b
     b

a               a

видимо если нет баланса 0, то есть переход от 1 к -1, можно порезать по нему, одну точку сюда, одну сюда.

Видимо поерил в такое решение

Я вот сидел и думал над примером, когда, если разбивать тупо примерно пополам (да-да, по количеству цветов, пропустил), не будет решения. Увы, не нашел. Если кто найдёт, буду рад увидеть)

Впрочем, ради научного интереса можно поискать архив с тестами (а заодно и разбор) и проверить. Вот только, боюсь, руки не дойдут. Еще много чего сделать нужно из запланированного =)

Rubanenko

Да, такое тоже кто-то писал.

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

Привет коллегам из Александрии =)

Примерно так оно и решается, я тогда в разбор не вникал =)

Proscriptus

Так как автор вопроса из Украины, то думаю, что разбор с Всеукраинской олимпиады подойдет. Задача под номером 3. http://uoi2010.kmpu.edu.ua/day2.pdf

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

acherepanov

NEERC 2007-2008 (Problem A). Там n ≤ 100, можно решать, находя минимальное взвешенное паросочетание (вес — длина отрезка).

PAG

Проведём вертикальную прямую через самую левую точку (если таких две, то верхнюю из них) и начнём вращать её вокруг этой точки, фиксируя прямую при прохождении её через очередную точку. Подсчитаем количество пройденных точек каждого цвета. Остановимся, когда число точек разных цветов будет одинаковым. При этом прямая разбивает исходное множество на 3 подмножества: две точки на этой прямой – они обязательно разного цвета и 2 подмножества, в каждом из которых равное число точек одного цвета (может быть ни одной). При этом отрезки, соединяющие точки разных подмножеств не пересекаются. Отметим точки на прямой и будем решать задачу для каждого из оставшихся множеств. На каждом шаге количество точек уменьшается- процесс конечен и приведёт к решению задачи.

Squire

Мне кажется, что такой метод "вращения прямой" поможет в том случае, когда нету условия неколлинеарности 3 точек, но заранее ведомо, что разбиение существует. Или я не совсем точно понял идею.

Условие, что никакие три точки не лежат на одной прямой, существенно. Оно означает, что прямая, проходящая через 2 любые точки разбивает множество данных точек на 3 подмножества: первое – состоит из 2 точек, лежащих на этой прямой, второе и третье – точки, расположенные в полуплоскостях, граница которых – эта прямая. При этом второе или третье множество могут быть пустыми. Если добиться, чтобы первое множество состояло из разноцветных точек, а в первом количество точек каждого цвета было одинаковым, то в третьем эти количества также будут равны. При этом отрезки, соединяющие точки второго множества не будут пересекать отрезки, соединяющие точки третьего множества. Зафиксировав отрезок, соединяющий точки первого множества, мы получим ту же задачу для второго и третьего множеств, количество точек в которых меньше исходного. Повторяя разбиение для каждого нового множества в конце концов соединим требуемым образом все точки исходного множества.

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