|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
01.12.2012, 11:03 | #1 |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
Геометрия Си/С++
Из заданного множества точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой, проходящей через эти точка, различались наименьшим образом.
Точки заданы координатами. Единственное что смог придумать это перебирать все пары точек, но это по времени получается достаточно долго. |
01.12.2012, 13:51 | #2 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Оптимизация: берём точку и все остальные точки загоняем в массив, дополняя каждую углом на неё из выбранной. Сортируем массив по углам. Теперь для каждой точки определение разности количества точек с одной и с другой стороны занимает логарифмическое время, всего в худшем случае O(N^2*lnN). Для чётного числа точек минимум 0 в среднем случае должен достигаться уже на первой-второй точке, что сокращает среднее время до O(N*lnN). Для нечётного числа точек всё хуже: вполне может быть единственная тройка точек, лежащая на одной прямой, разделяющей все остальные точки на две равномощные группы. В этом случае ничего умнее полного перебора мне в голову не приходит. А вот для чётного числа точек есть вторая оптимизация: взять произвольное направление прямой; найти, перебрав все точки, какая прямая с таким направлением делит множество точек пополам; если она неизбежно проводится по точкам и число этих точек нечётно - взять другое произвольное направление и повторить; если она может быть не проведена ни через одну точку - дальше попытаться чуть "подвинуть" или "довернуть" её. Если за несколько итераций этот алгоритм не срабатывает - значит, точки подобраны специально и очень аккуратно, рекомендуется возвращение к предыдущему алгоритму и полный перебор. |
|
01.12.2012, 15:25 | #3 |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
Код:
|
01.12.2012, 15:30 | #4 |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
да и точка находится не правильная)
|
01.12.2012, 15:44 | #5 |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
Код:
Код:
|
03.12.2012, 12:56 | #6 | |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
Цитата:
|
|
03.12.2012, 15:50 | #7 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Почему переменные целочисленные и подумали ли Вы про округление? Что за условие min!=1? Почему K считается от 1? И какие из этих проблем нельзя было обнаружить с помощью отладчика?.. |
|
03.12.2012, 16:23 | #8 |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
for(j=j+i тк фиксирую первую точку, смотрю пары с остальными точками. Про целочисленные переменные не подумал. min!=1 а разве это не будет минимальной разностью? Четное количество точек можно разделить пополам, нечетное либо так же пополам, либо с одной стороны будет на 1 точку больше чем с другой, от сюда условие не равенства 1. К надо считать от нуля?
|
03.12.2012, 17:41 | #9 | ||||
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Цитата:
Цитата:
Цитата:
Последний раз редактировалось Abstraction; 04.12.2012 в 09:29. |
||||
04.12.2012, 04:51 | #10 | |
Пользователь
Регистрация: 01.12.2012
Сообщений: 28
|
Цитата:
|
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
геометрия | novichokkk | Помощь студентам | 10 | 18.04.2012 18:36 |
Геометрия | Pascal.t | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 17.12.2010 00:13 |
Геометрия в Си | rik_nel | Общие вопросы C/C++ | 5 | 14.12.2010 13:43 |
Геометрия | zumm | Свободное общение | 3 | 07.07.2010 18:37 |
Си геометрия | Денни | Помощь студентам | 11 | 05.03.2010 09:41 |