Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.math.*;
- import java.security.*;
- import java.text.*;
- import java.util.*;
- import java.util.concurrent.*;
- import java.util.function.*;
- import java.util.regex.*;
- import java.util.stream.*;
- import static java.util.stream.Collectors.joining;
- import static java.util.stream.Collectors.toList;
- import static java.util.Collections.emptyList;
- import java.awt.geom.Point2D;
- class Result {
- public static int orientation(Point2D p1, Point2D p2,
- Point2D p3)
- {
- double val = (p2.getY() - p1.getY()) * (p3.getX() - p2.getX()) -
- (p2.getX() - p1.getX()) * (p3.getY() - p2.getY());
- if (Math.abs(val) < 0.0001) return 0;
- return (val >= 0.0001)? 1: 2;
- }
- public static List<Integer> fence_sort(List<List<Integer>> edges, int number_of_edges) {
- // Write your code here
- HashSet<Point2D> hs = new HashSet<Point2D>();
- Point2D start = new Point2D.Float(edges.get(0).get(0), edges.get(0).get(1));
- Point2D start_ = new Point2D.Float(edges.get(0).get(2), edges.get(0).get(3));
- for (List<Integer> edge : edges)
- {
- int x1 = edge.get(0);
- int y1 = edge.get(1);
- int x2 = edge.get(2);
- int y2 = edge.get(3);
- hs.add(new Point2D.Float(x1,y1));
- hs.add(new Point2D.Float(x2,y2));
- }
- int cnt =0;
- HashMap<Integer, Point2D> hashMap = new HashMap<Integer, Point2D>();
- HashMap<Point2D, Integer> pointMap = new HashMap<Point2D, Integer>();
- for (Point2D element : hs)
- {
- hashMap.put(cnt, element);
- pointMap.put(element, cnt++);
- }
- LinkedList<Integer> graph[] = new LinkedList[hs.size()];
- for (int i = 0; i < number_of_edges; i++) {
- graph[i] = new LinkedList();
- }
- for (List<Integer> edge : edges)
- {
- int x1 = edge.get(0);
- int y1 = edge.get(1);
- int x2 = edge.get(2);
- int y2 = edge.get(3);
- int u = pointMap.get(new Point2D.Float(x1,y1));
- int v = pointMap.get(new Point2D.Float(x2,y2));
- graph[u].add(v);
- graph[v].add(u);
- }
- boolean visited[] = new boolean[hs.size()];
- LinkedList<Integer> ans = new LinkedList<Integer>();
- int u_ = pointMap.get(start);
- int u1 = pointMap.get(start_);
- int u2 = -1;
- int neigh1 = graph[u_].get(0);
- int neigh2 = graph[u_].get(1);
- if(neigh1!=u1)
- u2 = neigh1;
- else
- u2 = neigh2;
- Point2D neig_p = hashMap.get(u2);
- int u=-1;
- int v=-1;
- if (orientation(neig_p, start, start_)==2)
- {
- u = u1;
- v = u_;
- }
- else if (orientation(neig_p, start, start_)==1)
- {
- u = u_;
- v = u1;
- }
- else
- {
- if (start.getY()<start_.getY())
- {
- u = u_;
- v = u1;
- }
- else
- {
- u = u1;
- v = u_;
- }
- }
- Arrays.fill(visited, false);
- visited[u]=true;
- ans.add((int)hashMap.get(u).getX());
- ans.add((int)hashMap.get(u).getY());
- ans.add((int)hashMap.get(v).getX());
- ans.add((int)hashMap.get(v).getY());
- while(visited[v]==false)
- {
- visited[v]=true;
- neigh1 = graph[v].get(0);
- neigh2 = graph[v].get(1);
- if(! visited[neigh1])
- {
- Point2D point = hashMap.get(neigh1);
- ans.add((int)point.getX());
- ans.add((int)point.getY());
- v = neigh1;
- }
- else if (! visited[neigh2])
- {
- Point2D point = hashMap.get(neigh2);
- ans.add((int)point.getX());
- ans.add((int)point.getY());
- v = neigh2;
- }
- else break;
- }
- return ans;
- }
- }
- public class Solution {
- public static void main(String[] args) throws IOException {
- BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
- BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
- int number_of_edges = Integer.parseInt(bufferedReader.readLine().trim());
- List<List<Integer>> edges = new ArrayList<>();
- IntStream.range(0, number_of_edges).forEach(i -> {
- try {
- edges.add(
- Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
- .map(Integer::parseInt)
- .collect(toList())
- );
- } catch (IOException ex) {
- throw new RuntimeException(ex);
- }
- });
- List<Integer> sorted_vertices = Result.fence_sort(edges, number_of_edges);
- bufferedWriter.write(
- sorted_vertices.stream()
- .map(Object::toString)
- .collect(joining(" "))
- + "\n"
- );
- bufferedReader.close();
- bufferedWriter.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement