написанные программы / задание №2 — 2 / VAR1 / lab_1_v1

{
Laboratory Task 1
~~~~~~~~~~~~~~~~~
Author is Aleksey Borzenkov, 2000
Copyright (c) NeOS Programming Software, 2000

(*) NeOS Programming Software is unregistered trademark, but you must do
(*) not use it!!! NeOS Programming Software was founded in 1998, and now
(*) contains only one member - its founder Aleksey Borzenkov.

(!) This program is specially designed for IFMO Technical University and
(!) the CTC ("Computer Technology and Control") faculty as a laboratory
(!) task with title "Pascal/150P.2 task number 1".

(?) But can be used as free software if you will found it useful. If you
(?) do so, the author ("Aleksey Borzenkov") gives you no warranty of any
(?) kind, and can only guarant that this program and all included files
(?) will occupy diskspace.
}
program L150P2_1;

const
nMaxPoints = 64; { ¬ ЄбЁ¬ «м­®Ґ Є®«-ў® в®зҐЄ }

type
{ ‘¤Ґ« ­® ¤«п «сЈЄ®© § ¬Ґ­л ­  Real, Single, Double Ё«Ё Extended }
TValueType = Real;

{ ЋЇЁблў Ґв в®зЄг }
TPoint = record
x, y: TValueType;
end;

{ ЋЇЁблў Ґв ¬ ббЁў в®зҐЄ }
TPointArray = array[1..nMaxPoints] of TPoint;

{ ЋЇЁблў Ґв ¬­®Ј®гЈ®«м­ЁЄ }
TPolygon = record
count: Integer;
point: TPointArray;
end;

{ ЋЇЁблў Ґв Ї®«®¦Ґ­ЁҐ в®зЄЁ ®в­®бЁвҐ«м­® ®в१Є  - "®аЁҐ­в жЁо" }
TPointPosition = (ppLeft, ppRight, ppBack, ppBetween, ppForward);
{^^^^^^^^^^^^^^^^^^^^^^^^^^^^}
{ Љ®««Ё­Ґ а­®бвм }
{____________________________}

var
{ ѓ«®Ў «м­лҐ ЇҐаҐ¬Ґ­­лҐ }
beVerbose: Boolean; { Ї®ўв®апвм «Ё ўў®¤ }

{
*-----------------------------------------------------------------------------
* integral_of_line: ўлзЁб«пҐв Ё­вҐЈа « ўҐЄв®а  (x1,y1) -> (x2,y2)
*
* га ў­Ґ­ЁҐ Їаאַ©:
*
* x-x1 y-y1 \ (x2-x1)y1 - (y2-y1)x1 y2-y1
* ------- = ------- ===> y = --------------------- + ----- x
* x2-x1 y2-y1 / x2-x1 x2-x1
*
* Ё­вҐЈа « зЁб«Ґ­­® а ўҐ­:
*
* x2
* Ъ
* і (x2-x1)y1 - (y2-y1)x1 + (y2-y1)x (x2-x1)(y2+y1)
* integral = і -------------------------------- dx = --------------
* і x2-x1 2
* Щ
* x1
*
*-----------------------------------------------------------------------------
}
function integral_of_line(x1, y1, x2, y2: TValueType): TValueType;
begin
integral_of_line := (x2 - x1) * (y2 + y1) / 2;
end;

{
*-----------------------------------------------------------------------------
* classify_point: ў®§ўа й Ґв Ї®«®¦Ґ­ЁҐ в®зЄЁ (x,y)
* ®в­®бЁвҐ«м­® ўҐЄв®а  (x1,y1) -> (x2,y2)
* ppLeft ppRight ppBack ppBetween ppForward
*-----------------------------------------------------------------------------
}
function classify_point(x1, y1, x2, y2, x, y: TValueType): TPointPosition;
var
ax, ay, bx, by, res: TValueType; { ¤«п Єа вЄ®бвЁ }
begin
ax := x - x1; ay := y - y1;
bx := x2 - x1; by := y2 - y1;
res := ax * by - bx * ay; { |a|*|b|*sin(b - a) }
if (res > 0) then
classify_point := ppRight
else if (res < 0) then
classify_point := ppLeft
else begin
res := ax * bx + ay * by; { |a|*|b|*cos(b - a) }
if (res < 0) then
classify_point := ppBack
else if (sqrt(ax*ax + ay*ay) <= sqrt(bx*bx + by*by)) then
classify_point := ppBetween
else
classify_point := ppForward;
end;
end;

{
*-----------------------------------------------------------------------------
* point_inside_polygon: ‚®§ўа й Ґв True, Ґб«Ё в®зЄ  (x,y) ў­гваЁ Ї®«ЁЈ®­ 
* ђҐи Ґвбп ¬Ґв®¤®¬ «гз 
*-----------------------------------------------------------------------------
}
function point_inside_polygon(x, y:TValueType; var polygon: TPolygon): Boolean;
function px(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do px := x;
end;
function py(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do py := y;
end;
var
i: Integer; { бзсвзЁЄ }
res: Boolean; { д« Ј ­Ґзсв­®бвЁ }
x1,y1,x2,y2: TValueType; { ¤«п Єа вЄ®бвЁ ўаҐ¬Ґ­­®Ґ еа ­Ё«ЁйҐ Є®®а¤Ё­ в }
begin
res := false;
point_inside_polygon := false;
for i := 1 to polygon.count do begin
x1 := px(i); y1 := py(i); x2 := px(i+1); y2 := py(i+1);
case classify_point(x1,y1,x2,y2,x,y) of
{ в Є Є Є бва®Ј®, в® Ґб«Ё ­  Ја ­ЁжҐ, в® ­Ґ ў­гваЁ }
ppBetween: exit;
{ «гз Ё¤св ўЇа ў® }
ppLeft:
if (y1 < y) and (y <= y2) then res := not res; { Ґб«Ё ®в१®Є бЇа ў  }
ppRight:
if (y2 < y) and (y <= y1) then res := not res; { Ґб«Ё ®в१®Є бЇа ў  }
end;
end;
point_inside_polygon := res; { Ґб«Ё ­Ґзсв­®Ґ зЁб«® а §, в® ў­гваЁ }
end;

{
*-----------------------------------------------------------------------------
* polygon_read: бзЁвлў Ґв Є®®а¤Ё­ вл ¬­®Ј®гЈ®«м­ЁЄ  б Є®­б®«Ё
*-----------------------------------------------------------------------------
}
procedure polygon_read(var polygon: TPolygon);
function px(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do px := x;
end;
function py(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do py := y;
end;
var
i, j: Integer; { бзсвзЁЄ в®зҐЄ Ё Ї®«®¦Ґ­Ёп }
begin
write('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® ўҐаиЁ­ (1-', nMaxPoints, '): ');
readln(polygon.count);
{ ¤Ґ« Ґ¬ не®, Ґб«Ё ­ ¤® }
if beVerbose then writeln(polygon.count:4);
if (polygon.count < 1) or (polygon.count > nMaxPoints) then
runerror(201); { Ї®¤­Ё¬ Ґ¬ runtime error 201: Range Check Error }
j := 1;
for i := 1 to polygon.count do begin
write('Љ®®а¤Ё­ вл ўҐаиЁ­л ­®¬Ґа ', i, ': ');
readln(polygon.point[j].x, polygon.point[j].y);
if beVerbose then
writeln(px(j):10:3, ' ', py(j):10:3);
if j = 1 then begin
inc(j); continue;
end;
{ ®вᥪ Ґ¬ ®¤Ё­ Є®ўлҐ в®зЄЁ }
if (px(j-1) = px(j)) and (py(j-1) = py(j)) then continue;
{ Ґб«Ё в®зҐЄ ўбҐЈ® ¤ўҐ, в® ¤Ґ« вм Ї®Є  ­ҐзҐЈ® }
if j = 2 then begin
inc(j); continue;
end;
{ ®вᥪ Ґ¬ в®зЄЁ, ­ е®¤пйЁҐбп ­  ®¤­®© Їаאַ© }
if classify_point(px(j-2),py(j-2),px(j-1),py(j-1),px(j),py(j)) = ppForward then begin
polygon.point[j-1].x := px(j);
polygon.point[j-1].y := py(j);
continue;
end;
{ зЁв Ґ¬ б«Ґ¤гойго в®зЄг }
inc(j);
end;
{ ॠ«м­л© а §¬Ґа ¬­®Ј®гЈ®«м­ЁЄ , Ї®б«Ґ ®вбҐзҐ­Ёп «Ёи­ҐЈ® }
polygon.count := j - 1;
end;

{
*-----------------------------------------------------------------------------
* polygon_area: ўлзЁб«пҐв Ї«®й ¤м ¬­®Ј®гЈ®«м­ЁЄ 
*-----------------------------------------------------------------------------
}
function polygon_area(var polygon: TPolygon): TValueType;
function px(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do px := x;
end;
function py(i: Integer): TValueType;
begin
with polygon.point[(i-1) mod polygon.count + 1] do py := y;
end;
var
i: Integer; { бзсвзЁЄ }
j: TValueType; { ўаҐ¬Ґ­­ п Ї«®й ¤м }
begin
j := 0;

for i := 1 to polygon.count do begin
j := j + integral_of_line(px(i), py(i), px(i+1), py(i+1));
end;

if j > 0 then begin
writeln('Њ­®Ј®гЈ®«м­ЁЄ ­ Їа ў«Ґ­ Ї® з б®ў®© бв५ЄҐ');
end else if j < 0 then begin
writeln('Њ­®Ј®гЈ®«м­ЁЄ ­ Їа ў«Ґ­ Їа®вЁў з б®ў®© бв५ЄЁ');
j := -j;
end;

polygon_area := j;
end;

{
*-----------------------------------------------------------------------------
* polygon_inside_polygon: ‚®§ўа й Ґв true, Ґб«Ё polygon2 ­ е®¤Ёвбп
* ў­гваЁ polygon1.
* ’®«мЄ® ¤«п ўлЇгЄ«ле!!!
* Re: ¤«п ў®Ј­гвле в Є¦Ґ ­ ¤® Їа®ўҐапвм ­ 
* ЇҐаҐбҐзҐ­ЁҐ бв®а®­.
*-----------------------------------------------------------------------------
}
function polygon_inside_polygon(var polygon1, polygon2: TPolygon): Boolean;
var
i: Integer;
begin
polygon_inside_polygon := false;
for i := 1 to polygon2.count do begin
{ Ґб«Ё е®вп Ўл ®¤­  в®зЄ  ­ е®¤Ёвбп б­ а¦Ё, в® ®­ ­Ґ ў­гваЁ }
if not point_inside_polygon(polygon2.point[i].x,
polygon2.point[i].y,
polygon1) then exit;
end;
{ Ґб«Ё ўбҐ в®зЄЁ ў­гваЁ, в® ®­ ў­гваЁ }
polygon_inside_polygon := true;
end;

{
*-----------------------------------------------------------------------------
* € ­ Є®­Ґж в®зЄ  ўе®¤  ў Їа®Ја ¬¬г
*-----------------------------------------------------------------------------
}
var
polygon1: TPolygon; { ¬­®Ј®гЈ®«м­ЁЄ 1 }
polygon2: TPolygon; { ¬­®Ј®гЈ®«м­ЁЄ 2 }
area1: TValueType; { Ї«®й ¤м 1 }
area2: TValueType; { Ї«®й ¤м 2 }
is_anybody_inside: Boolean;
begin
is_anybody_inside := false;
if (ParamCount >= 1) and (ParamStr(1) = 'verbose') then beVerbose := true
else beVerbose := false;

writeln('ъ-=* Њ­®Ј®гЈ®«м­ЁЄ 1 *=-ъ');
polygon_read(polygon1);
area1 := polygon_area(polygon1);
writeln('ъ-=* Џ«®й ¤м ¬­®Ј®гЈ®«м­ЁЄ  1 = ', area1:15:10, ' *=-ъ');

writeln('ъ-=* Њ­®Ј®гЈ®«м­ЁЄ 2 *=-ъ');
polygon_read(polygon2);
area2 := polygon_area(polygon2);
writeln('ъ-=* Џ«®й ¤м ¬­®Ј®гЈ®«м­ЁЄ  2 = ', area2:15:10, ' *=-ъ');

writeln('ъ-=* Љ Є®© Ё§ ¬­®Ј®гЈ®«м­ЁЄ®ў бва®Ј® ў­гваЁ ¤агЈ®Ј® *=-ъ');
if area1 > area2 then begin
is_anybody_inside := polygon_inside_polygon(polygon1, polygon2);
if is_anybody_inside then
writeln('‚в®а®© ­ е®¤Ёвбп ў­гваЁ ЇҐаў®Ј®');
end;
if area2 > area1 then begin
is_anybody_inside := polygon_inside_polygon(polygon2, polygon1);
if is_anybody_inside then
writeln('ЏҐаўл© ­ е®¤Ёвбп ў­гваЁ ўв®а®Ј®');
end;
if not is_anybody_inside then
writeln('ЌЁ®¤Ё­ Ё§ ¬­®Ј®гЈ®«м­ЁЄ®ў ­Ґ ­ е®¤Ёвбп ў­гваЁ ¤агЈ®Ј®');
writeln('ъ-=* Љ®­Ґж Їа®Ја ¬¬л *=-ъ');
end.