даны координаты N точек. найти такие две из них чтобы остальные точки располагались в разных сторонах отрезка(поровну) проходящего через эти две точки... например если N=6 то вправо от отрезка лежат 2 точки и влево также... помогите пожалуйста с реализацией алгоритма или подайте идею...
Sto
27.04.2007 0:47
А если будет непарное количество точек??
мисс_граффити
27.04.2007 0:48
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;
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
27.04.2007 11:13
если честно я ничего не понял в твоей программе ...я же не хотел графику ...в графике делфи я не разбираюсь ... if не трудно объясни что твоя прога делает
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.