Advertisement
Guest User

Untitled

a guest
Sep 30th, 2016
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.86 KB | None | 0 0
  1. import java.io.FileNotFoundException;
  2. import java.io.FileReader;
  3. import java.io.PrintWriter;
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.Collections;
  7. import java.util.HashMap;
  8. import java.util.Scanner;
  9.  
  10. public class HikingHills {
  11. public static void main(String[] args) throws FileNotFoundException {
  12. Scanner sc = new Scanner(new FileReader("hiking.in"));
  13. PrintWriter out = new PrintWriter("hiking.out");
  14.  
  15. N = sc.nextInt();
  16.  
  17. edgeList = new ArrayList<Edge>();
  18.  
  19. Triangle[] ts = new Triangle[N];
  20. unmap = new Point[N * 3 + 2];
  21.  
  22. for(int i = 0; i < N; i++) {
  23. Point p1 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
  24. Point p2 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
  25. Point p3 = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
  26.  
  27. if(!map.containsKey(p1)){
  28. unmap[nextNode] = p1;
  29. map.put(p1, nextNode++);
  30. }
  31.  
  32. if(!map.containsKey(p2)){
  33. unmap[nextNode] = p2;
  34. map.put(p2, nextNode++);
  35. }
  36.  
  37. if(!map.containsKey(p3)){
  38. unmap[nextNode] = p3;
  39. map.put(p3, nextNode++);
  40. }
  41.  
  42. ts[i] = new Triangle(p1, p2, p3);
  43. }
  44.  
  45. for(int i = 0; i < N; i++) {
  46. int node1 = map.get(ts[i].p1);
  47. int node2 = map.get(ts[i].p2);
  48. int node3 = map.get(ts[i].p3);
  49.  
  50. edgeList.add(new Edge(node1, node2, Math.max(ts[i].p1.z, ts[i].p2.z)));
  51. edgeList.add(new Edge(node1, node3, Math.max(ts[i].p1.z, ts[i].p3.z)));
  52. edgeList.add(new Edge(node2, node3, Math.max(ts[i].p2.z, ts[i].p3.z)));
  53.  
  54. edgeList.add(new Edge(node2, node1, Math.max(ts[i].p1.z, ts[i].p2.z)));
  55. edgeList.add(new Edge(node3, node1, Math.max(ts[i].p1.z, ts[i].p3.z)));
  56. edgeList.add(new Edge(node3, node2, Math.max(ts[i].p2.z, ts[i].p3.z)));
  57. }
  58.  
  59. Point start = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
  60.  
  61. Point end = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
  62.  
  63. if(!map.containsKey(start)){
  64. unmap[nextNode] = start;
  65. map.put(start, nextNode++);
  66. }
  67.  
  68. if(!map.containsKey(end)) {
  69. unmap[nextNode] = end;
  70. map.put(end, nextNode++);
  71. }
  72.  
  73. for(int i = 0; i < N; i++) {
  74. if(liesInTriangle(ts[i], start)) {
  75. int nodeStart = map.get(start);
  76. int node1 = map.get(ts[i].p1);
  77. int node2 = map.get(ts[i].p2);
  78. int node3 = map.get(ts[i].p3);
  79.  
  80. edgeList.add(new Edge(nodeStart, node1, Math.max(ts[i].p1.z, start.z)));
  81. edgeList.add(new Edge(nodeStart, node2, Math.max(ts[i].p2.z, start.z)));
  82. edgeList.add(new Edge(nodeStart, node3, Math.max(ts[i].p3.z, start.z)));
  83.  
  84. edgeList.add(new Edge(node1, nodeStart, Math.max(ts[i].p1.z, start.z)));
  85. edgeList.add(new Edge(node2, nodeStart, Math.max(ts[i].p2.z, start.z)));
  86. edgeList.add(new Edge(node3, nodeStart, Math.max(ts[i].p3.z, start.z)));
  87. }
  88.  
  89. if(liesInTriangle(ts[i], end)) {
  90. int nodeEnd = map.get(end);
  91. int node1 = map.get(ts[i].p1);
  92. int node2 = map.get(ts[i].p2);
  93. int node3 = map.get(ts[i].p3);
  94.  
  95. edgeList.add(new Edge(nodeEnd, node1, Math.max(ts[i].p1.z, end.z)));
  96. edgeList.add(new Edge(nodeEnd, node2, Math.max(ts[i].p2.z, end.z)));
  97. edgeList.add(new Edge(nodeEnd, node3, Math.max(ts[i].p3.z, end.z)));
  98.  
  99. edgeList.add(new Edge(node1, nodeEnd, Math.max(ts[i].p1.z, end.z)));
  100. edgeList.add(new Edge(node2, nodeEnd, Math.max(ts[i].p2.z, end.z)));
  101. edgeList.add(new Edge(node3, nodeEnd, Math.max(ts[i].p3.z, end.z)));
  102. }
  103. }
  104.  
  105. adjList = new ArrayList[nextNode];
  106.  
  107. for(int i = 0; i < nextNode; i++)
  108. adjList[i] = new ArrayList<Integer>();
  109.  
  110. Kruskal();
  111.  
  112. ans = new ArrayList<Integer>();
  113.  
  114. visited = new boolean[nextNode];
  115.  
  116. dfs(map.get(start), map.get(end));
  117.  
  118. Collections.reverse(ans);
  119.  
  120. out.println(ans.size());
  121.  
  122. for(int p : ans) {
  123. out.println(unmap[p]);
  124. }
  125.  
  126. out.flush();
  127. out.close();
  128. }
  129.  
  130. static boolean visited[];
  131. static ArrayList<Integer> ans;
  132. static boolean dfs(int u, int end) {
  133. if(u == end) {
  134. ans.add(end);
  135. return true;
  136. }
  137. visited[u] = true;
  138.  
  139. for(int v : adjList[u]) {
  140. if(!visited[v]){
  141. boolean reachFromV = dfs(v, end);
  142. if(reachFromV){
  143. ans.add(u);
  144. return true;
  145. }
  146. }
  147. }
  148.  
  149. return false;
  150. }
  151.  
  152. static boolean liesInTriangle(Triangle t, Point p) {
  153. Point p1 = t.p1;
  154. Point p2 = t.p2;
  155. Point p3 = t.p3;
  156.  
  157. double alpha = ((double)(p2.y - p3.y)*(p.x - p3.x) + (double)(p3.x - p2.x)*(p.y - p3.y)) /
  158. ((double)(p2.y - p3.y)*(p1.x - p3.x) + (double)(p3.x - p2.x)*(p1.y - p3.y));
  159. double beta = ((double)(p3.y - p1.y)*(p.x - p3.x) + (double)(p1.x - p3.x)*(p.y - p3.y)) /
  160. ((double)(p2.y - p3.y)*(p1.x - p3.x) + (double)(p3.x - p2.x)*(p1.y - p3.y));
  161. double gamma = 1.0f - alpha - beta;
  162.  
  163. return alpha >= 0 && beta >= 0 && gamma >= 0;
  164. }
  165.  
  166. static class Triangle {
  167. Point p1, p2, p3;
  168.  
  169. public Triangle(Point a, Point b, Point c) {
  170. p1 = a; p2 = b; p3 = c;
  171. }
  172. }
  173.  
  174. static class UnionFind {
  175.  
  176. int[] p,rank,setSize;
  177. int numSets;
  178.  
  179. public UnionFind(int N)
  180. {
  181. p = new int[N];
  182. rank = new int[N];
  183. setSize = new int[N];
  184.  
  185. for(int i=0; i<N; i++)
  186. p[i] = i;
  187.  
  188. numSets = N;
  189. Arrays.fill(setSize, 1);
  190. }
  191.  
  192. public int findSet(int i)
  193. {
  194. if(p[i] == i)
  195. return i;
  196.  
  197. int root = findSet(p[i]);
  198. p[i] = root; // Path compression
  199. return root;
  200. }
  201.  
  202. public boolean isSameSet(int i, int j)
  203. {
  204. return findSet(i) == findSet(j);
  205. }
  206.  
  207. public void unionSet(int i, int j)
  208. {
  209. int x = findSet(i);
  210. int y = findSet(j);
  211. if(x == y)
  212. return;
  213.  
  214. if(rank[x] > rank[y]){
  215. p[y] = x;
  216. setSize[x] += setSize[y];
  217. }
  218. else{
  219. p[x] = y;
  220. setSize[y] += setSize[x];
  221. }
  222.  
  223. if(rank[x] == rank[y])
  224. rank[y]++;
  225.  
  226. numSets--;
  227. }
  228.  
  229. public int numSets()
  230. {
  231. return numSets;
  232. }
  233.  
  234. public int setSize(int i)
  235. {
  236. return setSize[findSet(i)];
  237. }
  238.  
  239. }
  240.  
  241. static int nextNode = 0;
  242. static HashMap<Point, Integer> map = new HashMap<Point, Integer>();
  243. static Point[] unmap;
  244.  
  245. static ArrayList<Edge> edgeList;
  246. static ArrayList<Integer> adjList[];
  247.  
  248. static int N;
  249. static int Kruskal()
  250. {
  251. Collections.sort(edgeList);
  252.  
  253. int mst = 0;
  254. UnionFind uf = new UnionFind(nextNode);
  255.  
  256. for(Edge e : edgeList)
  257. if(!uf.isSameSet(e.u, e.v))
  258. {
  259. mst += e.w;
  260. uf.unionSet(e.u, e.v);
  261. adjList[e.u].add(e.v);
  262. adjList[e.v].add(e.u);
  263.  
  264. // System.out.println(e.u + " " + e.v);
  265. }
  266.  
  267. return mst;
  268. }
  269.  
  270.  
  271.  
  272. static class Edge implements Comparable<Edge>
  273. {
  274. int u,v,w;
  275. public Edge(int x, int y, int z)
  276. {
  277. u = x;
  278. v = y;
  279. w = z;
  280. }
  281. public int compareTo(Edge e) {
  282. return w - e.w;
  283. }
  284.  
  285. }
  286.  
  287. static class Point {
  288. int x,y,z;
  289.  
  290. Point(int x, int y, int z) {
  291. this.x = x;
  292. this.y = y;
  293. this.z = z;
  294. }
  295.  
  296. public boolean equals(Object o) {
  297. Point p = (Point) o;
  298. return x == p.x && y == p.y && z == p.z;
  299. }
  300.  
  301. public int hashCode() {
  302. return (new Integer(x).hashCode()
  303. + new Integer(y).hashCode()
  304. + new Integer(z).hashCode()) % ((int)1e9 + 7);
  305. }
  306.  
  307. public String toString() {
  308. return String.format("%d %d %d", x, y, z);
  309. }
  310. }
  311.  
  312.  
  313. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement