Guest User

Untitled

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