Guest User

Untitled

a guest
Oct 16th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. program Project1;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6. SysUtils;
  7.  
  8. type manT= record
  9. x: longint;
  10. y: longint;
  11. end;
  12. var b: array[1..100000]of manT;
  13. i, n, z, xx, c, f: longint;
  14. k, min: manT;
  15.  
  16. procedure Qsort(l , r:integer);
  17. var ll, rr: integer;
  18. begin
  19. ll:= l;
  20. rr:= r;
  21. z:= l+random(r-l+1);
  22. xx:= b[z].x;
  23. while ll<=rr do
  24. begin
  25. 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;
  26. 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;
  27. if ll<= rr then
  28. begin
  29. k:= b[ll];
  30. b[ll]:= b[rr];
  31. b[rr]:= k;
  32. ll:= ll+1;
  33. rr:= rr-1;
  34. end;
  35. end;
  36. if (l< rr) then Qsort(l, rr);
  37. if ll< r then Qsort(ll, r);
  38. end;
  39.  
  40. begin
  41. reset(input, 'input.txt');
  42. rewrite(output, 'output.txt');
  43.  
  44. readln(n);
  45.  
  46. for i:= 1 to n do
  47. readln(b[i].x, b[i].y);
  48.  
  49. {for i:=1 to n do
  50. writeln(b[i].x,' ',b[i].y); }
  51.  
  52. min.x:= b[1].x;
  53. min.y:= b[1].y;
  54.  
  55. for i:= 1 to n do
  56. if (b[i].x< min.x) or ((b[i].x= min.x)and(b[i].y< min.y)) then
  57. begin
  58. c:= i;
  59. min.x:= b[i].x;
  60. min.y:= b[i].y;
  61. end;
  62. f:= b[1].x;
  63. b[1].x:= b[c].x;
  64. b[c].x:= f;
  65. f:= b[1].y;
  66. b[1].y:= b[c].y;
  67. b[c].y:= f;
  68. writeln(min.x,' ', min.y);
  69. writeln;
  70. for i:=1 to n do
  71. writeln(b[i].x,' ', b[i].y);
  72.  
  73. for i:= 2 to n-1 do
  74. Qsort(1, n);
  75. writeln;
  76. for i:=1 to n do
  77. write(b[i].x, ' ', b[i].y);
  78.  
  79. close(input);
  80. close(output);
  81. end.
Add Comment
Please, Sign In to add comment