Помощь - Поиск - Пользователи - Календарь
Полная версия: линия проходящая через точки
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
даны координаты N точек. найти такие две из них чтобы остальные точки располагались в разных сторонах отрезка(поровну) проходящего через эти две точки...
например если N=6 то вправо от отрезка лежат 2 точки и влево также...
помогите пожалуйста с реализацией алгоритма lol.gif или подайте идею... blum.gif
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
если честно я ничего не понял в твоей программе nea.gif ...я же не хотел графику wacko.gif ...в графике делфи я не разбираюсь good.gif ... if не трудно объясни что твоя прога делает blum.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.