Source code for submission s1310

Go to diff to previous submission

Cockchaf.java

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Comparator;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.PriorityQueue;
  9. import java.util.Queue;
  10. import java.util.Scanner;
  11. import java.util.StringTokenizer;
  12.  
  13. public class Cockchaf {
  14. static class Step implements Comparable<Step>{
  15. Point p;
  16. double dx,dy,dz;
  17. double time;
  18.  
  19. Step (Point p_, double dx_, double dy_, double dz_,double time_){
  20. p = p_;
  21. dx = dx_;
  22. dy = dy_;
  23. dz = dz_;
  24. time = time_;
  25. }
  26.  
  27. public int compareTo(Step s) {
  28. double e = 0.0000001;
  29. if (s.time-time > e) return -1;
  30. if (time-s.time > e) return 1;
  31. return 0;
  32. }
  33. }
  34.  
  35. static class Point {
  36.  
  37. @Override
  38. public boolean equals(Object obj) {
  39. if (obj == null) {
  40. return false;
  41. }
  42. if (getClass() != obj.getClass()) {
  43. return false;
  44. }
  45. final Point other = (Point) obj;
  46. if (this.x != other.x) {
  47. return false;
  48. }
  49. if (this.y != other.y) {
  50. return false;
  51. }
  52. if (this.z != other.z) {
  53. return false;
  54. }
  55. return true;
  56. }
  57.  
  58. @Override
  59. public int hashCode() {
  60. int hash = 3;
  61. hash = 47 * hash + this.x;
  62. hash = 47 * hash + this.y;
  63. hash = 47 * hash + this.z;
  64. return hash;
  65. }
  66.  
  67. int x,y,z;
  68. double minT = Integer.MAX_VALUE;
  69. List<Point> e = new ArrayList<Point>();
  70.  
  71. Point(int x,int y, int z){
  72. this.x = x;
  73. this.y = y;
  74. this.z = z;
  75.  
  76. }
  77.  
  78. };
  79.  
  80. static double length(double x1, double x2, double x3, double y1, double y2, double y3){
  81. return Math.sqrt((x1-y1)*(x1-y1)+(x2-y2)*(x2-y2)+(x3-y3)*(x3-y3));
  82. }
  83.  
  84. static double degToTurn(double u1,double u2,double u3,double v1,double v2,double v3){
  85. double d;
  86. d = Math.acos((u1*v1+u2*v2+u3*v3)/(length(0,0,0,u1,u2,u3)*length(0,0,0,v1,v2,v3)));
  87. return d*180/Math.PI;
  88. }
  89.  
  90. public static void main(String[] args) throws IOException {
  91. //Scanner sc = new Scanner(System.in);
  92. do {
  93. String line = br.readLine();
  94. if(line == null) {
  95. break;
  96. }
  97. int N = Integer.parseInt(st.nextToken());
  98. int S = Integer.parseInt(st.nextToken());
  99. int T = Integer.parseInt(st.nextToken());
  100.  
  101. st = new StringTokenizer(br.readLine());
  102. Point end = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  103. Point start = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  104. List<Point> points = new ArrayList<Point>();
  105. points.add(start);
  106. points.add(end);
  107.  
  108. for (int i=0; i<N; i++){
  109. st = new StringTokenizer(br.readLine());
  110. Point p1 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  111. Point p2 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  112. if (p1.equals(p2)) continue;
  113. Point p1R = null, p2R = null;
  114. for (int j=0; j<points.size(); j++){
  115. if (points.get(j).equals(p1)){
  116. p1R = points.get(j);
  117. }
  118. if (points.get(j).equals(p2)){
  119. p2R = points.get(j);
  120. }
  121. if (p1R != null && p2R != null) break;
  122. }
  123. if (p1R == null){
  124. p1R = p1;
  125. points.add(p1R);
  126. }
  127. if (p2R == null){
  128. p2R = p2;
  129. points.add(p2R);
  130. }
  131.  
  132. p1R.e.add(p2R);
  133. p2R.e.add(p1R);
  134. }
  135.  
  136. /*Comparator<Step> comp = new Comparator<Step>(){
  137.  
  138.   public int compare(Step arg0, Step arg1) {
  139.   if (arg0.p == end && arg1.p != end){
  140.   return 1;
  141.   }else if (arg0.p != end && arg1.p == end){
  142.   return -1;
  143.   }
  144.   return arg0.compareTo(arg1);
  145.   }
  146.  
  147.   };*/
  148.  
  149. if (start.equals(end)){
  150. System.out.println("0.0000");
  151. continue;
  152. }
  153. Queue<Step> q = new PriorityQueue<Step>();
  154.  
  155. //init
  156. for (int i=0; i<start.e.size(); i++){
  157. double d = length(start.x, start.y, start.z, start.e.get(i).x, start.e.get(i).y, start.e.get(i).z);
  158. double dx = start.e.get(i).x - start.x;
  159. double dy = start.e.get(i).y - start.y;
  160. double dz = start.e.get(i).z - start.z;
  161. q.add(new Step(start.e.get(i), dx, dy, dz, d/S));
  162. //System.err.println(d/S);
  163. }
  164.  
  165. while (true) {
  166. Step c = q.poll();
  167. if (c.p.equals(end)){
  168. System.out.printf("%.4f\n", c.time);
  169. break;
  170. }
  171. for (int i=0; i<c.p.e.size(); i++){
  172. double d = length(c.p.x,c.p.y,c.p.z,c.p.e.get(i).x,c.p.e.get(i).y, c.p.e.get(i).z);
  173. double dx = c.p.e.get(i).x - c.p.x;
  174. double dy = c.p.e.get(i).y - c.p.y;
  175. double dz = c.p.e.get(i).z - c.p.z;
  176. double t = degToTurn(c.dx, c.dy, c.dz, dx, dy, dz);
  177. if (Math.abs(t-180) < 0.0000001) continue;
  178. double newTime = c.time + d/S + t/T;
  179. if (newTime < c.p.e.get(i).minT){
  180. c.p.e.get(i).minT = newTime;
  181. }
  182. if (newTime > c.p.e.get(i).minT+180/T){
  183. continue;
  184. }
  185. q.add(new Step(c.p.e.get(i), dx, dy, dz, newTime));
  186. }
  187. }
  188.  
  189. } while(true);
  190. }
  191.  
  192.  
  193. }
  194.  

Diff to submission s1247

Cockchaf.java

--- c4.s1247.cteam018.cockchaf.java.0.Cockchaf.java
+++ c4.s1310.cteam018.cockchaf.java.0.Cockchaf.java
@@ -66,4 +66,5 @@
         
         int x,y,z;
+        double minT = Integer.MAX_VALUE;
         List<Point> e = new ArrayList<Point>();
         
@@ -177,5 +178,12 @@
                     double t = degToTurn(c.dx, c.dy, c.dz, dx, dy, dz);
                     if (Math.abs(t-180) < 0.0000001) continue;
-                    q.add(new Step(c.p.e.get(i), dx, dy, dz, c.time + d/S + t/T));
+                    double newTime = c.time + d/S + t/T;
+                    if (newTime < c.p.e.get(i).minT){
+                      c.p.e.get(i).minT = newTime;  
+                    }
+                    if (newTime > c.p.e.get(i).minT+180/T){
+                        continue;
+                    }
+                    q.add(new Step(c.p.e.get(i), dx, dy, dz, newTime));
                 }
             }