Guest User

Untitled

a guest
Jul 18th, 2018
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.69 KB | None | 0 0
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.FileReader;
  4. import java.io.FileWriter;
  5. import java.io.IOException;
  6. import java.io.PrintWriter;
  7. import java.util.StringTokenizer;
  8.  
  9. import java.lang.Math;
  10. import java.util.Arrays;
  11.  
  12.  
  13. public class grMain implements Runnable {
  14. StringTokenizer st;
  15. BufferedReader in;
  16. PrintWriter out;
  17.  
  18.  
  19. public static class Point implements Comparable {
  20. int x;
  21. int y;
  22. int num;
  23. double angle;
  24. int range;
  25. public int compareTo(Object other) {
  26. Point vertex = (Point) other;
  27. if (angle - vertex.angle<0) {
  28. return -1;
  29. }
  30. if (angle - vertex.angle>0) {
  31. return 1;
  32. }
  33. if ((angle - vertex.angle)==0) {
  34. return (range-vertex.range);
  35. }
  36.  
  37. return 0;
  38.  
  39. }
  40. Point () {
  41.  
  42. }
  43. Point (int a) {
  44. num=a;
  45. }
  46.  
  47. }
  48.  
  49.  
  50. //variables
  51. Point points[];
  52.  
  53. int n;
  54. int min;
  55. int minI;
  56. Point minPoint;
  57.  
  58. int calcRange(Point a, Point b) {
  59. return (a.x-b.y)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
  60. }
  61. double calcAngle(Point a, Point b) {
  62. if ((b.x-a.x)!=0) {
  63. return Math.atan((b.y-a.y)/(b.x-a.x));
  64. } else {
  65. return Math.asin(1);
  66. }
  67. }
  68. public static void main(String[] args) {
  69. new Thread(new grMain()).run();
  70. }
  71.  
  72. public void run() {
  73. try {
  74. in = new BufferedReader(new FileReader("hull.in"));
  75. out = new PrintWriter(new FileWriter("hull.out"));
  76. solve();
  77. } catch (Exception e) {
  78. e.printStackTrace();
  79. } finally {
  80. out.flush();
  81. out.close();
  82. }
  83. }
  84.  
  85. String nextToken() throws IOException {
  86. while (st == null || !st.hasMoreTokens()) {
  87. st = new StringTokenizer(in.readLine());
  88. }
  89. return st.nextToken();
  90. }
  91.  
  92. int nextInt() throws NumberFormatException, IOException {
  93. return Integer.parseInt(nextToken());
  94. }
  95.  
  96. long nextLong() throws NumberFormatException, IOException {
  97. return Long.parseLong(nextToken());
  98. }
  99.  
  100. double nextDouble() throws NumberFormatException, IOException {
  101. return Double.parseDouble(nextToken());
  102. }
  103.  
  104. int ccw(Point p1, Point p2, Point p3){
  105. return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
  106.  
  107. }
  108. void solve() throws NumberFormatException, IOException {
  109. n=nextInt();
  110. int m=2;
  111. points=new Point[n];
  112. min=Integer.MAX_VALUE;
  113. minI=0;
  114. minPoint=new Point();
  115. for (int i=0; i<n; i++) {
  116. points[i]= new Point(i);
  117. }
  118. for (int i=0; i<n;i++) {
  119. points[i].x=nextInt();
  120. points[i].y=nextInt();
  121. if (points[i].x==min) {
  122. if (points[i].y<points[minI].y) {
  123. minI=i;
  124.  
  125. }
  126. }
  127. if (points[i].x<min) {
  128. min=points[i].x;
  129. minI=i;
  130. }
  131.  
  132.  
  133. }
  134. minPoint=points[minI];
  135. Point swap=points[minI];
  136. points[minI]=points[0];
  137. points[0]=swap;
  138. for (int i=0;i<n;i++) {
  139. points[i].angle=calcAngle(minPoint, points[i]);
  140. points[i].range=calcRange(minPoint,points[i]);
  141. }
  142. points[0].angle=-2;
  143.  
  144. Arrays.sort(points);
  145. for (int i=0;i<n;i++) {
  146. if (minPoint==points[i]) {
  147. swap=points[i];
  148. points[i]=points[0];
  149. points[0]=swap;
  150. }
  151. }
  152. //points[0]=points[n-1];
  153. for (int i=3; i<n; i++) {
  154. while (ccw(points[m-1],points[m],points[i])<=0) {
  155. m--;
  156. }
  157. m++;
  158. swap=points[m];
  159. points[m]=points[i];
  160. points[i]=swap;
  161. }
  162.  
  163. out.println(m+1);
  164. //out.print(minPoint.x+" "+minPoint.y+"\n");
  165. for (int i=0; i<m+1;i++) {
  166. out.print(points[i].x+" "+points[i].y+"\n");
  167. }
  168. }
  169. }
Add Comment
Please, Sign In to add comment