PDA

Просмотр полной версии : Медианы



Anonymous
13.09.2004, 23:30
Пожалуйста помогите решить задачу:

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

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

evgeny_d
14.09.2004, 08:01
Тут если доказать, что количество медиан зависит только от n (кол-ва точек) и не зависит от расположения точек, то можно рассматривать равносторонний многоугольник с n вершинами, у которого n/2 "медиан".

А вот как строго доказать первый факт надо подумать...

evgeny_d
14.09.2004, 08:09
А можно так.
Пусть всего n точек.
Тогда каждой точке x, очевидно, соответствует строго одна точка y из оставшихся n-1 точки, так чтобы пара (x,y) образовывала медиану (такая медиана существует для любой x, т.к. n-1 нечетно и никакие 3 точки не лежат на прямой).

Вспоминаем правило рукопожатия (если пара(x,y) образует медиану, то пара (y,x) образует ту же медиану, которую мы уже посчитали) и получаем результат - n/2

Anonymous
14.09.2004, 10:33
4 точки С коор-ми: (0;0), (3;0), (0;3), (1,1) - там 3 медианы.

evgeny_d
14.09.2004, 11:12
Да уж...
Значит предположение "если доказать, что количество медиан зависит только от n" не верно.
Тут еще один примерчик в голову пришел - (0,0)(0,4)(4,0)(1,1)(1,2)(2,1) - 6 точек, 6 медиан.

По любому условия прийдется ставить на взаимное расположение точек...
Правда для одного случая задача решена %))

В остальном - трудно сказать.

evgeny_d
14.09.2004, 14:25
А какого объема множество, с которым прийдется работать?
Если небольшое - то почему бы просто не перебрать все пары и для каждой посмотреть, является ли она медианой (подставлять в уравнение прямой, полученной по двум точкам значение третьей точки, чтобы определить, с какой стороны эта третья точка, т.е. сравнивать полученно значение с 0).

Т.е. порядка n(n-1)/2 операций на перебор ребер и порядка (n-2) операции на перебор точек.
Итого такой алгоритм будет за O(n^3) находить не только количество медиан, но и все медианы.

Или надо более быстрый алгоритм?

Anonymous
15.09.2004, 00:06
Организовал перебор...
Может кто-нибудь протестит?
-----------------------------------------------------------
program Mediani;
var
x,y: array[1..250] of Integer;
i,j,k: Integer;
sver,sniz,med,n: Byte;
begin
Write('Введите кол-во точек: '); ReadLn(n);
for i:=1 to n do
begin
Write('Введите координаты ',i,'-ой точки: ');
Read(x[i],y[i]);
end;
med:=0;
for i:=1 to n-1 do
begin
for j:=i+1 to n do
begin
sver:=0;
sniz:=0;
for k:=1 to n do
begin
if ((y[k]-y[i])*(x[j]-x[i]) > (x[k]-x[i])*(y[j]-y[i]))
then
inc(sver)
else
if ((y[k]-y[i])*(x[j]-x[i]) < (x[k]-x[i])*(y[j]-y[i]))
then
inc(sniz);
end;
if sver = sniz
then
inc(med);
end;
end;
WriteLn('Кол-во медиан: ',med);
end.
----------------------------------------------------------------------

Naeel Maqsudov
15.09.2004, 08:00
Все естественно порушится, если хотя бы у двух точек координата Y будет одинакова.