| Цитата(Akina @ 14.9.2004, 08:43) |
| Если N - количество точек, то количество медиан = N/2. |
Точно не верно, вот контрпример, возьмём 4 точки С коор-ми: (0;0), (3;0), (0;3), (1,1) - там 3 медианы
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Медианы |
| Автор: DmitryG. 13.9.2004, 22:24 |
| Пожалуйста, подскажите алгоритм решения задачи: Дано четное число точек на плоскости, причем никакие три из них не лежат на одной прямой. Медианой этого множества точек называется прямая, соединяющая две точки множества и такая, что с обеих сторон от нее расположено равное число точек. Подсчитать количество медиан. Заранее спасибо! |
| Автор: Akina 14.9.2004, 08:43 |
| Если N - количество точек, то количество медиан = N/2. |
| Автор: Fearless 14.9.2004, 09:04 |
| полностью согласен c Akina |
| Автор: 3,14 14.9.2004, 09:23 | ||
Точно не верно, вот контрпример, возьмём 4 точки С коор-ми: (0;0), (3;0), (0;3), (1,1) - там 3 медианы |
| Автор: val 14.9.2004, 09:27 |
| 3,14 прав... Надо еще подумать... |
| Автор: Dmitry G. 14.9.2004, 09:31 |
| А если бы точек было нечетное количество...? Какого ваше мнение насчет задачи: решаема, нерешаема? |
| Автор: 3,14 14.9.2004, 09:47 | ||
По любому задача решается полным перебором, вычислительная сложность алгоритма - вот в чём вопрос. |
| Автор: dargaard 14.9.2004, 10:39 | ||
тогда будет 0 медиан - всегда с однои стороны будет четное кол-во точек а с другои нечетное (так как по условию три точки не могут быть на однои прямои) |
| Автор: dargaard 14.9.2004, 11:19 |
| просто идея сортируем точки (от меншего х-а к болшемы и от меншего y к болшему. например вышли у нас точки A,B,C,D) далше соединяем A-B-C-D-A если вышел выпуклыи многоугольник - то медиан будет N/2. а вот если он вогнутыи то не знаю , есть тока смутные предположения - по моему выидет что то типа N/2 + 1*V где V количество вогнутостеи. (предположение нет времени пока проверить) |
| Автор: 3,14 14.9.2004, 11:42 | ||
извиняюсь если не правильно понял, вот результат такой сортировки : 1 - (0;0) 2 - (0;3) 3 - (1;1) 4 - (3;1) 5 - (3;3) 6 - (4;2) Соединяем : 1->2->3->4->5->6->1 - многоугольника не выходит, получаем пересечение |
| Автор: Akina 14.9.2004, 12:31 |
| Да, погорячился... количество медиан гарантированно N/2 <= M <= N-1 Это можно доказать... а вот ПОДСЧИТАТЬ - это фактически НАЙТИ их все... тут кроме перебора вряд ли что придумаешь - вернее придумать можно, но вряд ли вычислительно это будет лучше прямого перебора... |
| Автор: dargaard 14.9.2004, 21:33 |
| 3,14 прогнал я немного - с чегота взял что так всегда получится многоугольник  бум думать дальше |
| Автор: Akina 15.9.2004, 08:09 |
| 1) Если все точки являются вершинами выпуклого многоугольника, тогда M = N/2 2) (пока только неоконченная мысль...) Из любого количества точек можно выбрать часть из них так, что они являются вершинами выпуклого многоугольника, описанного вокруг всех остальных точек. Правда как это прикрутить к РЕШЕНИЮ задачи - пока не знаю... |
| Автор: redrick 19.9.2004, 01:36 |
| ребят, а откуда уверенность существования алгоритма лучше перебора ? я вот в серьёз задумался над доказательством его отсутствия |
| Автор: dargaard 19.9.2004, 02:26 |
| нет уверенности - просто полным перебором как то неинтересно, да и хочется верить что можно решить задачу не за N! переборов |
| Автор: redrick 19.9.2004, 02:38 |
| задача произвольная (под n! мы ведь понимаем гарантированное, т. е. в худшем случае решение, а не среднее время вычисления) - соответственно - если вы как-то упорядочиваете комбинацию, то достачно привести пример, когда такое упорядочиние невозможно... такие вот мысли |
| Автор: maxim1000 19.9.2004, 11:35 | ||
разве речь идет о n! ??? если тупым перебором - n^3 если немного оптимизированным - n^2 |
| Автор: dargaard 19.9.2004, 11:55 |
| maxim1000 а как ты собираешься переберать за n^3? напиши решение - интересно посмотреть. |
| Автор: maxim1000 19.9.2004, 14:00 | ||
я думал, будет интересно, как это сделать за n^2 ...тогда для начала n^3, а потом - n^2: ---- всего возможных прямых n*(n-1)/2 для каждой прямой проверяем, является ли она медианой - (n-2) операций воти получаем n*(n-1)*(n-2)/2 операций, т.е. n^3 ---- если немного модифицировать, можно делать так: 1. выбираем одну точку, находим для нее все медианы 2. как находить медианы с фиксированным концом: 2.1. проектируем все остальные точки на окружность с центром в выбранной точке (т.к. расстояния абсолютно неважны, важны только направления) 2.2. выбираем от фонаря одну из точек, спроектированных на окружность 2.3. строим прямую из центра окружности к выбранной 2.4. считаем количество точек справа/слева 2.5. если совпало - добавляем медиану в список 2.6. немного поворачиваем прямую (например, по часовой стрелке) - выбираем следующую точку на окружности так, чтобы поворот был минимален (она может быть с одной стороны или с другой стороны от предыдущей), обновляем количества точек справа/слева 2.7. jump 2.5. вот и получается, что для проверки на "медианность" при повороте не надо каждый раз пересчитывать количества точек справа/слева сложность получается порядка n^2... ---- вот, даже рисуночек изобразил  |
| Автор: redrick 19.9.2004, 18:21 | ||||
при таком алгоритме мы, возможно, будем болтаться между 2-мя точками (они ближайшие друг для друга) - так что наверно запоминать придется.
что пудово - если новая точка будет лежать на том же радиусе, что и старая, то суммы изменятся на 1, если на противоположном - не изменятся. но первый аргумент остается в силе - нужно обеспечить проверку всех вариантов... или там не может быть такой ситуации о которой я говорю ? + проецирование - для квадрата не существенно, а вот если до линейного доберемся - косяк будет =) |
| Автор: maxim1000 19.9.2004, 20:26 | ||||||
это я плохо выразился:
направление вращения выбирается один раз навсегда если начали вращаться по часовой стрелке, то так и будет вращать
а это как? если можно, примерчик |
| Автор: maxim1000 19.9.2004, 22:21 |
| упс... заметил один пробой... для того, чтобы быстро находить следующую точку, надо, чтобы они были отсортированы, а для этого нужно n*log(n) так что получается n*n*log(n)... |
| Автор: redrick 19.9.2004, 23:44 |
| мои вопросы сняты =) |