Type TPoint = Record X, Y: Double; End; TLine = Record Start, Finish: TPoint; End; Const maxN = 400; var N: Integer; i: Integer; P: array [1 .. MaxN] of TPoint; { Points array } Used: array [1 .. MaxN] of Boolean; Lines: array[1 .. maxN] Of TLine; nLines, pred_line: integer; iLines, iPoints, currLine, currPoint: Integer; First,Point,NewPoint: Integer; procedure WritePoint(i: Integer); begin Writeln('[',i:3,'] (',P[i].x:4:0, ';', P[i].y:4:0, ')'); end; function Bigger(P,P1,P2: TPoint): Boolean; begin Bigger := (P1.x - P.x) * (P2.y - P.y) - (P1.y - P.y) * (P2.x - P.x) > 0; end; procedure write_line(i: integer); begin with lines[i] do begin Write('start : '); Writeln('[',i:3,'] (', start.x:4:0, ';', start.y:4:0, ')'); Write('finish: '); Writeln('[',i:3,'] (', finish.x:4:0, ';', finish.y:4:0, ')'); end; WriteLn; end; Function Distance(S: TLine; P: TPoint): Double; procedure VSub(var res: TPoint; a, b: TPoint); begin res.x := a.x - b.x; res.y := a.y - b.y; end; Procedure VAdd(var res: TPoint; a, b: TPoint); begin res.x := a.x + b.x; res.y := a.y + b.y; end; procedure VScale(Var res: TPoint; a: TPoint; f: Double); begin res.x := a.x * f; res.y := a.y * f; end; function VDot(u, v: TPoint): double; begin VDot := u.x * v.x + u.y * v.y; end; function Dist(u, v: TPoint): double; var x: tpoint; begin VSub(X, u, v); Dist := sqrt(VDot(X, X)); end; var T, Pb, v, w: TPoint; b, c1, c2: double; begin VSub(v, s.finish, s.start); VSub(w, p, s.start); c1 := VDot(w, v); If c1 <= 0 Then Distance := Dist(P, S.Start) Else Begin c2 := VDot(v, v); If c2 <= c1 Then Distance := Dist(P, S.Finish) Else Begin VScale(T, v, (c1 / c2)); VAdd(Pb, S.Start, T); distance := Dist(p, Pb); End; End; end; var min_dist, d: double; was_changed: boolean; begin Write('Amount of Points: '); Readln(N); First:=1; for i:=1 to N do begin Write('Point #', i:3, ' Coords [X Y]: '); Readln(P[i].x, P[i].y); if (P[i].y < P[First].y) then First:=i else if (P[i].y = P[First].y) and (P[i].x < P[First].x) then First:=i; end; FillChar(Used,SizeOf(Used),False); Writeln('Hull points: '); Point:=First; nLines := 0; repeat Inc(nLines); if nLines > 1 then Lines[nLines - 1].Finish := P[Point]; Lines[nLines].Start := P[Point]; WritePoint(Point); Used[Point]:=True; NewPoint:=0; for i:=1 to N do if i <> Point then begin if (NewPoint = 0) or (Bigger(P[Point], P[i], P[NewPoint])) then NewPoint:=i; end; Point:=NewPoint; until Point = First; Lines[nLines].Finish := Lines[1].Start; repeat was_changed := false; min_dist := 10000; for iPoints := 1 to N do if not used[iPoints] then begin was_changed := true; for iLines := 1 to nLines do begin D := Distance(Lines[iLines], P[iPoints]); If D < min_dist then begin min_dist := D; currLine := iLines; currPoint := iPoints; end; end; end; if was_changed then begin move(lines[currline+1], lines[currline+2], (nlines - currline+1)*sizeof(TLine)); lines[currline].finish := p[currpoint]; lines[currline+1].start := p[currpoint]; if currline = nlines then lines[currline+1].finish := lines[1].start else lines[currline+1].finish := lines[currline+2].start; inc(nlines); used[currpoint] := true; end; until not was_changed; writeln('Polygon lines:'); for i := 1 to nLines do write_line(i); end.