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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.03.2009, 05:51
Ground

 
Сообщений: n/a

Алгоритм по определению пересечения линий
Всем доброго времени суток!
Есть вот такая задачка: даны 10к точек, координаты положительны. Если их соединить, то получиться ломаная. Нужно провести линию, соединяющую две любых точки, чтоб эта линия не пересекала ломаную, и образовывала многоугольник с ломаной, с максимальной площадью. Каким алгоритмом можно это было бы реализовать?
Небольшой рисунок: http://pic.ipicture.ru/uploads/090321/2CJq5ygWDh.jpg

Я попробовал через перебор точек в цикле, но быстродействие оставляет желать лучшего - программа выполняется порядка 8-10 секунд, вместо необходимых 1-3. У меня выходит 2 цикла по 10к точек, я перебираю пары 1-3, 1-4, ..., 1-10к, после 2-4, 2-5, ..., 2-10к, и так до 9998-10к. Это получается 10к^2 вычислений.
  #2  
Старый 28.03.2009, 06:12
Новичок

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

Еще немного о моем текущем алгоритме:
Код:
//Задаем пербор точек по принципу 1-1, 1-2, 1-m, 2-1, m-m
		for(int i=0; i<m; i++) {
			for(int j=i+2; j<m; j++) {
				int k=1;
//Перебираем точки (k штук) между i-j, ищем пересечение с ломаной.
				while(k<j-i) {
//Тут у нас проверка на пересечние, если есть, то делаем break;
//Или, если прошли все иттерации k, то высчитываем площадь.
                                             }
                                  }
                       }
Вот примерно так все это выглядит. Я пропустил кучу структур if-else if-else в цикле while, но они на основной алгоритм не влияют.
  #3  
Старый 31.03.2009, 00:48
Новичок

Отправить личное сообщение для e-maxx Посмотреть профиль Найти все сообщения от e-maxx
 
Регистрация: 14.03.2009
Сообщений: 24

Ваше решение - это не 10k^2, а уже 10k^3 (циклы по i,j,k, каждый порядка 10k).

Можно попробовать такую идею использовать. Для фиксированных i и j должно выполняться, что для всех точек k (i<k<j), их полярные углы относительно точки i должны быть строго больше полярного угла для j. Тогда видится совсем простое решение за квадрат: во внешнем цикле перебираем i, внутри него храним текущий минимум полярного угла относительно i, и делаем цикл по j; смотрим на полярный угол точки j, если он строго меньше текущего минимума, то текущий многоугольник - хороший, надо проапдейтить ответ его площадью (а площадь вроде тоже можно по ходу цикла по j, считать, а не каждый раз с нуля).
  #4  
Старый 31.03.2009, 16:14
Новичок

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

Хотелось бы узнать, что брать за минимум, что принимать полярной осью, относительно чего высчитывать угол?
Как я понял, за полярную ось мы берем ось ОХ. И тогда: (см рисунок)
Зеленая линия с ОХ образует угол A. Забиваем его в минимум. Проходим цикл по j. Для i+1 нет смысла вычислять, смотрим j=i+2. Синяя линия образует угол B. Он меньше A. Все верно, для данного случая алгоритм работает. Смотрим для j=i+3. Угол образуемый зеленой линией меньше, но линия i-j пересекает ломаную. Алгоритм не работает.
PS: Возмножно я неверно понял ваш алгоритм.

UPD: После долгих размышлений я наконец понял принцип. Написал. Работает. Теперь осталось понять, как по ходу программы высчитывать площадь.
Изображения:
Тип файла: jpg Untitled-2.jpg (33.5 Кб, 97 просмотров)

Последний раз редактировалось Ground, 01.04.2009 в 10:31.
  #5  
Старый 05.04.2009, 17:42
Новичок

Отправить личное сообщение для e-maxx Посмотреть профиль Найти все сообщения от e-maxx
 
Регистрация: 14.03.2009
Сообщений: 24

Ну площадь для любого многоугольника можно посчитать так: просуммировать знаковые площади треугольников (P[0],P[i-1],P[i]) по всем i, и в конце взять модуль от суммы - это и будет площадью. Знаковая площадь - это которая при обходе треугольника в одну сторону (напр., по часовой стрелке) всегда даёт положительный результат, а в обратную - отрицательный.
Вся "хитрость" такого суммирования знаковых площадей - что все "лишние" прибавленные площади всё равно в итоге сократятся.

Ну тогда и очевидно, как поддерживать текущую площадь многоугольника...
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычисление пересечения vilza Реализация, исходники, языки 7 30.01.2009 16:58
Определить точки пересечения эллипсов like-nix Математические алгоритмы 3 13.10.2008 18:15
площадь пересечения многоугольников Artemon Вычислительная геометрия 1 20.03.2008 13:45
Утончение линий на Delphi varvara16 Реализация, исходники, языки 3 17.03.2008 23:38
проверка пересечения dex Вычислительная геометрия 1 27.02.2007 07:52