Олимпиадные задачи по программированию. Ч. 2. Лучшие решения. Ускова О.Ф - 18 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Программа:
{Автор: Вахтин А. А.}
program CrossLine;
Type TPoint=Record
X,Y: Real;
End;
{Массив точек, задающих линии. Максимальное число линий 100}
TLines=Array [1..100,1..2] of TPoint;
{Массив точек пересечений линий. Максимальное число точек пересечений 4950 (по
комбинаторике )}
TPoints=Array [1..4950] of TPoint;
Var F: Text;
p: TPoint;
Lines: TLines;
Points: TPoints;
n,k,i,j: Integer;
Count: Integer;
pcount: Integer;
x1,y1,x2,y2: Integer;
Function Cross(x11,y11,x21,y21,x12,y12,x22,y22: Real): Boolean;
Var a1,b1,c1: Real;
a2,b2,c2: Real;
p: TPoint;
i: Integer;
Begin
Cross:=true;
{Задаются параметры прямых (ay+bx=c}
a1:=x21-x11;
b1:=y11-y21;
c1:=a1*y11+b1*x11;
a2:=x22-x12;
b2:=y12-y22;
c2:=a2*y12+b2*x12;
{Если линии совпадают}
If (a1*b2-a2*b1=0) and (a1*b2=a2*b1) and (b1*c2=b2*c1)
and (a1*c2=a2*c1) then Cross:=false;
{Если линии пересекаются }
If a1*b2-a2*b1<>0 then
Begin
{Ищется точка пересечений}
p.x:=(a1*c2-a2*c1)/(a1*b2-a2*b1);
p.y:=(b2*c1-b1*c2)/(a1*b2-a2*b1);
i:=1;
{Пароверка наличия точки пересечений в массиве . Если нет - добавляется}
While (i<=pcount) and ((p.x<>Points[i].x)
or (p.y<>Points[i].y)) do i:=i+1;
If (pcount=0) or (i>pcount) then
Begin
Inc(pcount);
Points[pcount]:=p;
End;
End;
end;{Cross}

Страницы