Advertisement
kiril_cvetkov

Untitled

Jun 8th, 2020
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.48 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.*;
  3. import java.security.*;
  4. import java.text.*;
  5. import java.util.*;
  6. import java.util.concurrent.*;
  7. import java.util.function.*;
  8. import java.util.regex.*;
  9. import java.util.stream.*;
  10. import static java.util.stream.Collectors.joining;
  11. import static java.util.stream.Collectors.toList;
  12. import static java.util.Collections.emptyList;
  13. import java.awt.geom.Point2D;
  14.  
  15.  
  16.  
  17. class Result {
  18.  
  19. public static int orientation(Point2D p1, Point2D p2,
  20. Point2D p3)
  21. {
  22.  
  23. double val = (p2.getY() - p1.getY()) * (p3.getX() - p2.getX()) -
  24. (p2.getX() - p1.getX()) * (p3.getY() - p2.getY());
  25.  
  26. if (Math.abs(val) < 0.0001) return 0;
  27.  
  28. return (val >= 0.0001)? 1: 2;
  29. }
  30.  
  31.  
  32. public static List<Integer> fence_sort(List<List<Integer>> edges, int number_of_edges) {
  33. // Write your code here
  34. HashSet<Point2D> hs = new HashSet<Point2D>();
  35. Point2D start = new Point2D.Float(edges.get(0).get(0), edges.get(0).get(1));
  36. Point2D start_ = new Point2D.Float(edges.get(0).get(2), edges.get(0).get(3));
  37.  
  38. for (List<Integer> edge : edges)
  39. {
  40. int x1 = edge.get(0);
  41. int y1 = edge.get(1);
  42. int x2 = edge.get(2);
  43. int y2 = edge.get(3);
  44. hs.add(new Point2D.Float(x1,y1));
  45. hs.add(new Point2D.Float(x2,y2));
  46.  
  47. }
  48. int cnt =0;
  49. HashMap<Integer, Point2D> hashMap = new HashMap<Integer, Point2D>();
  50. HashMap<Point2D, Integer> pointMap = new HashMap<Point2D, Integer>();
  51. for (Point2D element : hs)
  52. {
  53. hashMap.put(cnt, element);
  54. pointMap.put(element, cnt++);
  55. }
  56. LinkedList<Integer> graph[] = new LinkedList[hs.size()];
  57. for (int i = 0; i < number_of_edges; i++) {
  58. graph[i] = new LinkedList();
  59. }
  60.  
  61. for (List<Integer> edge : edges)
  62. {
  63. int x1 = edge.get(0);
  64. int y1 = edge.get(1);
  65. int x2 = edge.get(2);
  66. int y2 = edge.get(3);
  67. int u = pointMap.get(new Point2D.Float(x1,y1));
  68. int v = pointMap.get(new Point2D.Float(x2,y2));
  69. graph[u].add(v);
  70. graph[v].add(u);
  71. }
  72. boolean visited[] = new boolean[hs.size()];
  73.  
  74. LinkedList<Integer> ans = new LinkedList<Integer>();
  75. int u_ = pointMap.get(start);
  76. int u1 = pointMap.get(start_);
  77. int u2 = -1;
  78.  
  79. int neigh1 = graph[u_].get(0);
  80. int neigh2 = graph[u_].get(1);
  81.  
  82. if(neigh1!=u1)
  83. u2 = neigh1;
  84.  
  85. else
  86. u2 = neigh2;
  87.  
  88. Point2D neig_p = hashMap.get(u2);
  89.  
  90. int u=-1;
  91. int v=-1;
  92.  
  93. if (orientation(neig_p, start, start_)==2)
  94. {
  95. u = u1;
  96. v = u_;
  97. }
  98. else if (orientation(neig_p, start, start_)==1)
  99. {
  100. u = u_;
  101. v = u1;
  102. }
  103. else
  104. {
  105. if (start.getY()<start_.getY())
  106. {
  107. u = u_;
  108. v = u1;
  109. }
  110. else
  111. {
  112. u = u1;
  113. v = u_;
  114. }
  115. }
  116.  
  117. Arrays.fill(visited, false);
  118. visited[u]=true;
  119. ans.add((int)hashMap.get(u).getX());
  120. ans.add((int)hashMap.get(u).getY());
  121. ans.add((int)hashMap.get(v).getX());
  122. ans.add((int)hashMap.get(v).getY());
  123.  
  124. while(visited[v]==false)
  125. {
  126. visited[v]=true;
  127. neigh1 = graph[v].get(0);
  128. neigh2 = graph[v].get(1);
  129. if(! visited[neigh1])
  130. {
  131. Point2D point = hashMap.get(neigh1);
  132. ans.add((int)point.getX());
  133. ans.add((int)point.getY());
  134. v = neigh1;
  135. }
  136. else if (! visited[neigh2])
  137. {
  138. Point2D point = hashMap.get(neigh2);
  139. ans.add((int)point.getX());
  140. ans.add((int)point.getY());
  141. v = neigh2;
  142. }
  143. else break;
  144. }
  145.  
  146. return ans;
  147.  
  148. }
  149.  
  150. }
  151.  
  152. public class Solution {
  153. public static void main(String[] args) throws IOException {
  154. BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  155. BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  156.  
  157. int number_of_edges = Integer.parseInt(bufferedReader.readLine().trim());
  158.  
  159. List<List<Integer>> edges = new ArrayList<>();
  160.  
  161. IntStream.range(0, number_of_edges).forEach(i -> {
  162. try {
  163. edges.add(
  164. Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
  165. .map(Integer::parseInt)
  166. .collect(toList())
  167. );
  168. } catch (IOException ex) {
  169. throw new RuntimeException(ex);
  170. }
  171. });
  172.  
  173. List<Integer> sorted_vertices = Result.fence_sort(edges, number_of_edges);
  174.  
  175. bufferedWriter.write(
  176. sorted_vertices.stream()
  177. .map(Object::toString)
  178. .collect(joining(" "))
  179. + "\n"
  180. );
  181.  
  182. bufferedReader.close();
  183. bufferedWriter.close();
  184. }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement