Пожалуйста, подскажите алгоритм решения задачи:

Дано четное число точек на плоскости, причем никакие три из них не лежат на одной прямой. Медианой этого множества точек называется прямая, соединяющая две точки множества и такая, что с обеих сторон от нее расположено равное число точек. Подсчитать количество медиан.

Заранее спасибо!

Если N - количество точек, то количество медиан = N/2.

полностью согласен c Akina

Цитата(Akina @ 14.9.2004, 08:43)

Если N - количество точек, то количество медиан = N/2.

Точно не верно, вот контрпример, возьмём 4 точки С коор-ми: (0;0), (3;0), (0;3), (1,1) - там 3 медианы

3,14 прав... Надо еще подумать...

А если бы точек было нечетное количество...?

Какого ваше мнение насчет задачи: решаема, нерешаема?

Цитата(Dmitry @ 14.9.2004, 09:31)

А если бы точек было нечетное количество...? Какого ваше мнение насчет задачи: решаема, нерешаема?

По любому задача решается полным перебором, вычислительная сложность алгоритма - вот в чём вопрос.

Это сообщение отредактировал(а) 3,14 - 14.9.2004, 09:48

Цитата(Dmitry @ 13.9.2004, 22:31)

А если бы точек было нечетное количество...?

тогда будет 0 медиан - всегда с однои стороны будет четное кол-во точек а с другои нечетное (так как по условию три точки не могут быть на однои прямои)

просто идея
сортируем точки (от меншего х-а к болшемы и от меншего y к болшему. например вышли у нас точки A,B,C,D)
далше соединяем A-B-C-D-A
если вышел выпуклыи многоугольник - то медиан будет N/2.
а вот если он вогнутыи то не знаю , есть тока смутные предположения - по моему выидет что то типа N/2 + 1*V где V количество вогнутостеи. (предположение нет времени пока проверить)

Цитата

сортируем точки (от меншего х-а к болшемы и от меншего y к болшему. например вышли у нас точки A,B,C,D) далше соединяем A-B-C-D-A

извиняюсь если не правильно понял, вот результат такой сортировки :
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 - многоугольника не выходит, получаем пересечение

Да, погорячился... количество медиан гарантированно

N/2 <= M <= N-1

Это можно доказать... а вот ПОДСЧИТАТЬ - это фактически НАЙТИ их все... тут кроме перебора вряд ли что придумаешь - вернее придумать можно, но вряд ли вычислительно это будет лучше прямого перебора...

3,14
прогнал я немного - с чегота взял что так всегда получится многоугольник бум думать дальше

1) Если все точки являются вершинами выпуклого многоугольника, тогда M = N/2

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

Правда как это прикрутить к РЕШЕНИЮ задачи - пока не знаю...

ребят, а откуда уверенность существования алгоритма лучше перебора ?
я вот в серьёз задумался над доказательством его отсутствия

нет уверенности - просто полным перебором как то неинтересно, да и хочется верить что можно решить задачу не за N! переборов

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

такие вот мысли

Цитата

нет уверенности - просто полным перебором как то неинтересно, да и хочется верить что можно решить задачу не за N! переборов

разве речь идет о n! ???
если тупым перебором - n^3
если немного оптимизированным - n^2

maxim1000
а как ты собираешься переберать за n^3? напиши решение - интересно посмотреть.

Цитата

а как ты собираешься переберать за n^3? напиши решение - интересно посмотреть.

я думал, будет интересно, как это сделать за 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...
----
вот, даже рисуночек изобразил

Цитата

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

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

Цитата

вот и получается, что для проверки на "медианность" при повороте не надо каждый раз пересчитывать количества точек справа/слева

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


но первый аргумент остается в силе - нужно обеспечить проверку всех вариантов... или там не может быть такой ситуации о которой я говорю ?

+ проецирование - для квадрата не существенно, а вот если до линейного доберемся - косяк будет =)

Цитата

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

это я плохо выразился:

Цитата

немного поворачиваем прямую (например, по часовой стрелке)

направление вращения выбирается один раз навсегда
если начали вращаться по часовой стрелке, то так и будет вращать

Цитата

+ проецирование - для квадрата не существенно, а вот если до линейного доберемся - косяк будет =)

а это как? если можно, примерчик

Это сообщение отредактировал(а) maxim1000 - 19.9.2004, 20:28

упс... заметил один пробой...
для того, чтобы быстро находить следующую точку, надо, чтобы они были отсортированы, а для этого нужно n*log(n)
так что получается n*n*log(n)...

мои вопросы сняты =)