Source code for submission s1247

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. List<Point> e = new ArrayList<Point>();
  69.  
  70. Point(int x,int y, int z){
  71. this.x = x;
  72. this.y = y;
  73. this.z = z;
  74.  
  75. }
  76.  
  77. };
  78.  
  79. static double length(double x1, double x2, double x3, double y1, double y2, double y3){
  80. return Math.sqrt((x1-y1)*(x1-y1)+(x2-y2)*(x2-y2)+(x3-y3)*(x3-y3));
  81. }
  82.  
  83. static double degToTurn(double u1,double u2,double u3,double v1,double v2,double v3){
  84. double d;
  85. d = Math.acos((u1*v1+u2*v2+u3*v3)/(length(0,0,0,u1,u2,u3)*length(0,0,0,v1,v2,v3)));
  86. return d*180/Math.PI;
  87. }
  88.  
  89. public static void main(String[] args) throws IOException {
  90. //Scanner sc = new Scanner(System.in);
  91. do {
  92. String line = br.readLine();
  93. if(line == null) {
  94. break;
  95. }
  96. int N = Integer.parseInt(st.nextToken());
  97. int S = Integer.parseInt(st.nextToken());
  98. int T = Integer.parseInt(st.nextToken());
  99.  
  100. st = new StringTokenizer(br.readLine());
  101. Point end = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  102. Point start = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  103. List<Point> points = new ArrayList<Point>();
  104. points.add(start);
  105. points.add(end);
  106.  
  107. for (int i=0; i<N; i++){
  108. st = new StringTokenizer(br.readLine());
  109. Point p1 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  110. Point p2 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  111. if (p1.equals(p2)) continue;
  112. Point p1R = null, p2R = null;
  113. for (int j=0; j<points.size(); j++){
  114. if (points.get(j).equals(p1)){
  115. p1R = points.get(j);
  116. }
  117. if (points.get(j).equals(p2)){
  118. p2R = points.get(j);
  119. }
  120. if (p1R != null && p2R != null) break;
  121. }
  122. if (p1R == null){
  123. p1R = p1;
  124. points.add(p1R);
  125. }
  126. if (p2R == null){
  127. p2R = p2;
  128. points.add(p2R);
  129. }
  130.  
  131. p1R.e.add(p2R);
  132. p2R.e.add(p1R);
  133. }
  134.  
  135. /*Comparator<Step> comp = new Comparator<Step>(){
  136.  
  137.   public int compare(Step arg0, Step arg1) {
  138.   if (arg0.p == end && arg1.p != end){
  139.   return 1;
  140.   }else if (arg0.p != end && arg1.p == end){
  141.   return -1;
  142.   }
  143.   return arg0.compareTo(arg1);
  144.   }
  145.  
  146.   };*/
  147.  
  148. if (start.equals(end)){
  149. System.out.println("0.0000");
  150. continue;
  151. }
  152. Queue<Step> q = new PriorityQueue<Step>();
  153.  
  154. //init
  155. for (int i=0; i<start.e.size(); i++){
  156. double d = length(start.x, start.y, start.z, start.e.get(i).x, start.e.get(i).y, start.e.get(i).z);
  157. double dx = start.e.get(i).x - start.x;
  158. double dy = start.e.get(i).y - start.y;
  159. double dz = start.e.get(i).z - start.z;
  160. q.add(new Step(start.e.get(i), dx, dy, dz, d/S));
  161. //System.err.println(d/S);
  162. }
  163.  
  164. while (true) {
  165. Step c = q.poll();
  166. if (c.p.equals(end)){
  167. System.out.printf("%.4f\n", c.time);
  168. break;
  169. }
  170. for (int i=0; i<c.p.e.size(); i++){
  171. 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);
  172. double dx = c.p.e.get(i).x - c.p.x;
  173. double dy = c.p.e.get(i).y - c.p.y;
  174. double dz = c.p.e.get(i).z - c.p.z;
  175. double t = degToTurn(c.dx, c.dy, c.dz, dx, dy, dz);
  176. if (Math.abs(t-180) < 0.0000001) continue;
  177. q.add(new Step(c.p.e.get(i), dx, dy, dz, c.time + d/S + t/T));
  178. }
  179. }
  180.  
  181. } while(true);
  182. }
  183.  
  184.  
  185. }
  186.  

Diff to submission s1217

Cockchaf.java

--- c4.s1217.cteam018.cockchaf.java.0.Cockchaf.java
+++ c4.s1247.cteam018.cockchaf.java.0.Cockchaf.java
@@ -161,5 +161,5 @@
                 double dz = start.e.get(i).z - start.z;
                 q.add(new Step(start.e.get(i), dx, dy, dz, d/S));
-                System.err.println(d/S);
+                //System.err.println(d/S);
             }
             
@@ -176,4 +176,5 @@
                     double dz = c.p.e.get(i).z  - c.p.z;
                     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));
                 }