Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- program Project1;
- {$APPTYPE CONSOLE}
- uses
- SysUtils;
- type manT= record
- x: longint;
- y: longint;
- end;
- var b: array[1..100000]of manT;
- i, n, z, xx, c, f: longint;
- k, min: manT;
- procedure Qsort(l , r:integer);
- var ll, rr: integer;
- begin
- ll:= l;
- rr:= r;
- z:= l+random(r-l+1);
- xx:= b[z].x;
- while ll<=rr do
- begin
- while (i<=n) and ((b[i].x-min.x)*(b[i+1].y-min.y)-(b[i+1].x-min.x)*(b[i].y-min.y))<0 do ll:=ll+1;
- while (j>=1) and ((b[i].x-min.x)*(b[i+1].y-min.y)-(b[i+1].x-min.x)*(b[i].y-min.y))>0 do rr:=rr-1;
- if ll<= rr then
- begin
- k:= b[ll];
- b[ll]:= b[rr];
- b[rr]:= k;
- ll:= ll+1;
- rr:= rr-1;
- end;
- end;
- if (l< rr) then Qsort(l, rr);
- if ll< r then Qsort(ll, r);
- end;
- begin
- reset(input, 'input.txt');
- rewrite(output, 'output.txt');
- readln(n);
- for i:= 1 to n do
- readln(b[i].x, b[i].y);
- {for i:=1 to n do
- writeln(b[i].x,' ',b[i].y); }
- min.x:= b[1].x;
- min.y:= b[1].y;
- for i:= 1 to n do
- if (b[i].x< min.x) or ((b[i].x= min.x)and(b[i].y< min.y)) then
- begin
- c:= i;
- min.x:= b[i].x;
- min.y:= b[i].y;
- end;
- f:= b[1].x;
- b[1].x:= b[c].x;
- b[c].x:= f;
- f:= b[1].y;
- b[1].y:= b[c].y;
- b[c].y:= f;
- writeln(min.x,' ', min.y);
- writeln;
- for i:=1 to n do
- writeln(b[i].x,' ', b[i].y);
- for i:= 2 to n-1 do
- Qsort(1, n);
- writeln;
- for i:=1 to n do
- write(b[i].x, ' ', b[i].y);
- close(input);
- close(output);
- end.
Add Comment
Please, Sign In to add comment