линия проходящая через точки, разделить точки поровну Опции

[Bard]

даны координаты N точек. найти такие две из них чтобы остальные точки располагались в разных сторонах отрезка(поровну) проходящего через эти две точки...
например если N=6 то вправо от отрезка лежат 2 точки и влево также...
помогите пожалуйста с реализацией алгоритма или подайте идею...

[Sto]

А если будет непарное количество точек??

[мисс_граффити]

1. По разные стороны отрезка? Может, все-таки прямой?
2. Наверное, в точной формулировке не "поровну", а "чтобы разница была минимальной"? (при N=7, например, поровну не получится).
У меня есть дельфийская реализация.
Изменения коснутся только рисования... Ты же просил идеи по алгоритмам... так что выкладываю.

типы данных, которые нам потребуются:

type
TPoint=record
  x,y:integer;
  end;
TLine=record
  A,B,C:real;
  end;
TPointSet=array [1..50] of TPoint;

глобальные переменные:

var i,j,Dif,MinDif,OnLineCurrent,Point1,Point2:integer;
  P1,P2: TPoint;
  L: TLine;
  S:TPointSet;

вспомогательные подпрограммы:

  procedure InitLine(var L: TLine; pA,pB: TPoint);
  begin
  L.A:=pB.y-pA.y;
  L.B:=pA.x-pB.x;
  L.C:=pA.y*(pB.x-pA.x)-pA.x*(pB.y-pA.y);
  end;

  function SignPoint(L:TLine;P:TPoint):integer;
  var r:real;
  begin
  r:=L.A*P.x+L.B*P.y+L.C;
  if abs®<=0.001 then
    SignPoint:=0
  else
    if r<0 then
      SignPoint:=-1
    else
      SignPoint:=1;
  end;

  function Difference (L:TLine;S:TPointSet;var OnLineCurrent: integer):integer;
  var D,i,Temp:byte;
  begin
  D:=0;
  OnLineCurrent:=0;
  for i:=1 to 20 do
    begin
    Temp:=SignPoint(L,S[i]);
    D:=D+Temp;
    if Temp=0 then
      OnLineCurrent:=OnLineCurrent+1;
    end;
  Difference:=abs(D);
  end;

Основная часть программы (вот в нее тебе придется вносить изменения).

begin
randomize;
Image1.Canvas.Brush.Color:=clWhite;
Image1.Canvas.Rectangle(0,0,700,700);
for i:=1 to 20 do
  begin
  S[i].x:=random(350);
  S[i].y:=random(300);
  Image1.Canvas.Pen.Color:=clBlack;
  Image1.Canvas.Brush.Color:=clRed;
  Image1.Canvas.Ellipse(S[i].x-2,S[i].y-2,S[i].x+2,S[i].y+2);
  end;
for i:=1 to 19 do
  begin
  if MinDif=0 then break;
    for j:=i+1 to 20 do
      begin
      if MinDif=0 then break;
      InitLine(L,S[i],S[j]);
      Dif:=Difference(L,S,OnLineCurrent);
      if MinDif>Dif then
        begin
        MinDif:=Dif;
        Point1:=i;
        Point2:=j;
        end;
      end;
    end;
  with Image1.Canvas do
  begin
  Pen.Color:=clRed;
  MoveTo(S[Point1].x,S[Point1].y);
  LineTo(S[Point2].x,S[Point2].y);
  end;
end;

end.

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

[Bard]

если честно я ничего не понял в твоей программе ...я же не хотел графику ...в графике делфи я не разбираюсь ... if не трудно объясни что твоя прога делает