задача произвольная (под 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)...

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