Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.10.2007, 16:22
Новичок

Отправить личное сообщение для Lomir Посмотреть профиль Найти все сообщения от Lomir
 
Регистрация: 24.09.2006
Сообщений: 3

Пересечение отрезков
Дана окружность поделеная на N<=1000000000 равный частей. Точки раздела пронумерованы против часовой стрелки от 1 до N. Точка с номером 1 находить в верху.

В нутри окружности проверены K <=5000 отрезков. Отрезок задаеться 2мя номерами точек на окружности.

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

Начальные данные:
7 4
1 6
3 7
2 4
6 4

Ответ:
1

Есть какие нибуть идеи? Кажеться в общем виде задача на минимальное удаление отрезков сводить в мин покрытию графа, а это NP полная задача. А тут чего делать то?

Последний раз редактировалось Lomir, 08.10.2007 в 16:26.
  #2  
Старый 08.10.2007, 16:36
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Возможно, здесь подойдет структура данных "дерево отрезков", интервальное дерево, interval tree
  #3  
Старый 22.10.2007, 22:50
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

Применим динамику.
Каждый отрезок разбивает круг на две части. Мы для каждого отрезка будем хранить ответ для левой и правых частей. Найдем его просто перебирая первый отрезок, который будет после текущего, ну и считая ответ для него. Время работы K^2.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пересечение двух отрезков в 3d. незарегистрированный Математические алгоритмы 1 25.01.2007 12:17