Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.FileNotFoundException;
- import java.io.FileReader;
- import java.io.PrintWriter;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.Scanner;
- public class HikingHills {
- public static void main(String[] args) throws FileNotFoundException {
- Scanner sc = new Scanner(new FileReader("hiking.in"));
- PrintWriter out = new PrintWriter("hiking.out");
- N = sc.nextInt();
- edgeList = new ArrayList<Edge>();
- Triangle[] ts = new Triangle[N];
- unmap = new Point[N * 3 + 2];
- for(int i = 0; i < N; i++) {
- Point p1 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
- Point p2 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
- Point p3 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
- if(!map.containsKey(p1)){
- unmap[nextNode] = p1;
- map.put(p1, nextNode++);
- }
- if(!map.containsKey(p2)){
- unmap[nextNode] = p2;
- map.put(p2, nextNode++);
- }
- if(!map.containsKey(p3)){
- unmap[nextNode] = p3;
- map.put(p3, nextNode++);
- }
- ts[i] = new Triangle(p1, p2, p3);
- }
- for(int i = 0; i < N; i++) {
- int node1 = map.get(ts[i].p1);
- int node2 = map.get(ts[i].p2);
- int node3 = map.get(ts[i].p3);
- edgeList.add(new Edge(node1, node2, Math.max(ts[i].p1.z, ts[i].p2.z)));
- edgeList.add(new Edge(node1, node3, Math.max(ts[i].p1.z, ts[i].p3.z)));
- edgeList.add(new Edge(node2, node3, Math.max(ts[i].p2.z, ts[i].p3.z)));
- edgeList.add(new Edge(node2, node1, Math.max(ts[i].p1.z, ts[i].p2.z)));
- edgeList.add(new Edge(node3, node1, Math.max(ts[i].p1.z, ts[i].p3.z)));
- edgeList.add(new Edge(node3, node2, Math.max(ts[i].p2.z, ts[i].p3.z)));
- }
- Point start = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
- Point end = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
- if(!map.containsKey(start)){
- unmap[nextNode] = start;
- map.put(start, nextNode++);
- }
- if(!map.containsKey(end)) {
- unmap[nextNode] = end;
- map.put(end, nextNode++);
- }
- for(int i = 0; i < N; i++) {
- if(liesInTriangle(ts[i], start)) {
- int nodeStart = map.get(start);
- int node1 = map.get(ts[i].p1);
- int node2 = map.get(ts[i].p2);
- int node3 = map.get(ts[i].p3);
- edgeList.add(new Edge(nodeStart, node1, Math.max(ts[i].p1.z, start.z)));
- edgeList.add(new Edge(nodeStart, node2, Math.max(ts[i].p2.z, start.z)));
- edgeList.add(new Edge(nodeStart, node3, Math.max(ts[i].p3.z, start.z)));
- edgeList.add(new Edge(node1, nodeStart, Math.max(ts[i].p1.z, start.z)));
- edgeList.add(new Edge(node2, nodeStart, Math.max(ts[i].p2.z, start.z)));
- edgeList.add(new Edge(node3, nodeStart, Math.max(ts[i].p3.z, start.z)));
- }
- if(liesInTriangle(ts[i], end)) {
- int nodeEnd = map.get(end);
- int node1 = map.get(ts[i].p1);
- int node2 = map.get(ts[i].p2);
- int node3 = map.get(ts[i].p3);
- edgeList.add(new Edge(nodeEnd, node1, Math.max(ts[i].p1.z, end.z)));
- edgeList.add(new Edge(nodeEnd, node2, Math.max(ts[i].p2.z, end.z)));
- edgeList.add(new Edge(nodeEnd, node3, Math.max(ts[i].p3.z, end.z)));
- edgeList.add(new Edge(node1, nodeEnd, Math.max(ts[i].p1.z, end.z)));
- edgeList.add(new Edge(node2, nodeEnd, Math.max(ts[i].p2.z, end.z)));
- edgeList.add(new Edge(node3, nodeEnd, Math.max(ts[i].p3.z, end.z)));
- }
- }
- adjList = new ArrayList[nextNode];
- for(int i = 0; i < nextNode; i++)
- adjList[i] = new ArrayList<Integer>();
- Kruskal();
- ans = new ArrayList<Integer>();
- visited = new boolean[nextNode];
- dfs(map.get(start), map.get(end));
- Collections.reverse(ans);
- out.println(ans.size());
- for(int p : ans) {
- out.println(unmap[p]);
- }
- out.flush();
- out.close();
- }
- static boolean visited[];
- static ArrayList<Integer> ans;
- static boolean dfs(int u, int end) {
- if(u == end) {
- ans.add(end);
- return true;
- }
- visited[u] = true;
- for(int v : adjList[u]) {
- if(!visited[v]){
- boolean reachFromV = dfs(v, end);
- if(reachFromV){
- ans.add(u);
- return true;
- }
- }
- }
- return false;
- }
- static boolean liesInTriangle(Triangle t, Point p) {
- Point p1 = t.p1;
- Point p2 = t.p2;
- Point p3 = t.p3;
- double alpha = ((double)(p2.y - p3.y)*(p.x - p3.x) + (double)(p3.x - p2.x)*(p.y - p3.y)) /
- ((double)(p2.y - p3.y)*(p1.x - p3.x) + (double)(p3.x - p2.x)*(p1.y - p3.y));
- double beta = ((double)(p3.y - p1.y)*(p.x - p3.x) + (double)(p1.x - p3.x)*(p.y - p3.y)) /
- ((double)(p2.y - p3.y)*(p1.x - p3.x) + (double)(p3.x - p2.x)*(p1.y - p3.y));
- double gamma = 1.0f - alpha - beta;
- return alpha >= 0 && beta >= 0 && gamma >= 0;
- }
- static class Triangle {
- Point p1, p2, p3;
- public Triangle(Point a, Point b, Point c) {
- p1 = a; p2 = b; p3 = c;
- }
- }
- static class UnionFind {
- int[] p,rank,setSize;
- int numSets;
- public UnionFind(int N)
- {
- p = new int[N];
- rank = new int[N];
- setSize = new int[N];
- for(int i=0; i<N; i++)
- p[i] = i;
- numSets = N;
- Arrays.fill(setSize, 1);
- }
- public int findSet(int i)
- {
- if(p[i] == i)
- return i;
- int root = findSet(p[i]);
- p[i] = root; // Path compression
- return root;
- }
- public boolean isSameSet(int i, int j)
- {
- return findSet(i) == findSet(j);
- }
- public void unionSet(int i, int j)
- {
- int x = findSet(i);
- int y = findSet(j);
- if(x == y)
- return;
- if(rank[x] > rank[y]){
- p[y] = x;
- setSize[x] += setSize[y];
- }
- else{
- p[x] = y;
- setSize[y] += setSize[x];
- }
- if(rank[x] == rank[y])
- rank[y]++;
- numSets--;
- }
- public int numSets()
- {
- return numSets;
- }
- public int setSize(int i)
- {
- return setSize[findSet(i)];
- }
- }
- static int nextNode = 0;
- static HashMap<Point, Integer> map = new HashMap<Point, Integer>();
- static Point[] unmap;
- static ArrayList<Edge> edgeList;
- static ArrayList<Integer> adjList[];
- static int N;
- static int Kruskal()
- {
- Collections.sort(edgeList);
- int mst = 0;
- UnionFind uf = new UnionFind(nextNode);
- for(Edge e : edgeList)
- if(!uf.isSameSet(e.u, e.v))
- {
- mst += e.w;
- uf.unionSet(e.u, e.v);
- adjList[e.u].add(e.v);
- adjList[e.v].add(e.u);
- // System.out.println(e.u + " " + e.v);
- }
- return mst;
- }
- static class Edge implements Comparable<Edge>
- {
- int u,v,w;
- public Edge(int x, int y, int z)
- {
- u = x;
- v = y;
- w = z;
- }
- public int compareTo(Edge e) {
- return w - e.w;
- }
- }
- static class Point {
- int x,y,z;
- Point(int x, int y, int z) {
- this.x = x;
- this.y = y;
- this.z = z;
- }
- public boolean equals(Object o) {
- Point p = (Point) o;
- return x == p.x && y == p.y && z == p.z;
- }
- public int hashCode() {
- return (new Integer(x).hashCode()
- + new Integer(y).hashCode()
- + new Integer(z).hashCode()) % ((int)1e9 + 7);
- }
- public String toString() {
- return String.format("%d %d %d", x, y, z);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement