Source code for submission s1330

Go to diff to previous submission

Cockchaf.java

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.PriorityQueue;
  7. import java.util.Scanner;
  8.  
  9. public class Cockchaf {
  10. 	private static class Vrch implements Comparable<Vrch>{
  11. 		public double d;
  12. 		public Vrchol v;
  13. 		public Vrchol p;
  14.  
  15. 		public Vrch(double d, Vrchol v, Vrchol p) {
  16. 			this.d = d;
  17. 			this.v = v;
  18. 			this.p = p;
  19. 		}
  20.  
  21. 		@Override
  22. 		public int compareTo(Vrch o) {
  23. 			return (int)Math.signum(o.d-d);
  24. 		}
  25.  
  26. 	}
  27.  
  28. 	public static double a2(double a){
  29. 		return a*a;
  30. 	}
  31.  
  32. 	private static class Vrchol{
  33. 		public int x,y,z,p;
  34. 		public List<Vrchol> sused;
  35.  
  36. 		public Vrchol(int x, int y, int z) {
  37. 			this.x = x;
  38. 			this.y = y;
  39. 			this.z = z;
  40. 			sused = new LinkedList<Vrchol>();
  41. 		}
  42.  
  43. 		public double vzdialenost(Vrchol v){
  44. 			return Math.sqrt(a2(v.x-x)+a2(v.y-y)+a2(v.z-z));
  45. 		}
  46.  
  47.  
  48. 		public boolean equals(Vrchol v) {
  49. 			if(v.x==x && v.y==y && v.z==z){
  50. 				return true;
  51. 			} else {
  52. 				return false;
  53. 			}
  54. 		}
  55.  
  56. 		@Override
  57. 		public String toString() {
  58. 			return "[" + x + ","+y+","+z+"] ";
  59. 		}
  60. 	}
  61.  
  62. 	private static double uhol(Vrchol v1, Vrchol v2, Vrchol v3){
  63. 		int dx1 = v2.x-v1.x;
  64. 		int dy1 = v2.y-v1.y;
  65. 		int dz1 = v2.z-v1.z;
  66.  
  67. 		int dx2 = v3.x-v2.x;
  68. 		int dy2 = v3.y-v2.y;
  69. 		int dz2 = v3.z-v2.z;
  70.  
  71. 		return (Math.acos((dx1*dx2 + dy1*dy2 + dz1*dz2) / (Math.sqrt(a2(dx1)+a2(dy1)+a2(dz1)) * Math.sqrt(a2(dx2)+a2(dy2)+a2(dz2))))/Math.PI*180);		
  72. 	}
  73.  
  74. 	public static void main(String[] args) {
  75. 		String line;
  77. 		while(true){
  78. 			try {
  79. 				line = br.readLine();
  80. 				Scanner sc = new Scanner(line);
  81. 				int N = sc.nextInt();
  82. 				int S = sc.nextInt();
  83. 				int T = sc.nextInt();
  84. 				List<Vrchol> zoznam = new ArrayList<Vrchol>();
  85. 				for(int i=0; i<= N; ++i){
  86. 					line = br.readLine();
  87. 					sc = new Scanner(line);
  88. 					int x1 = sc.nextInt();
  89. 					int y1 = sc.nextInt();
  90. 					int z1 = sc.nextInt();
  91. 					Vrchol nv1 = new Vrchol(x1, y1, z1);
  92.  
  93. 					int x2 = sc.nextInt();
  94. 					int y2 = sc.nextInt();
  95. 					int z2 = sc.nextInt();
  96. 					Vrchol nv2 = new Vrchol(x2, y2, z2);
  97.  
  98. 					boolean jv1 = false, jv2 = false;
  99. 					for(Vrchol v: zoznam){
  100. 						if(v.equals(nv1)){
  101. 							nv1 = v;
  102. 							jv1 = true;
  103. 						}
  104. 						if(v.equals(nv2)){
  105. 							nv2 = v;
  106. 							jv2 = true;
  107. 						}
  108. 						if(jv1 && jv2){
  109. 							break;
  110. 						}
  111. 					}
  112.  
  113. 					if(!jv1) zoznam.add(nv1);
  114. 					if(!jv2) zoznam.add(nv2);
  115. 					if(i!=0){
  116. 						nv1.sused.add(nv2);
  117. 						nv2.sused.add(nv1);
  118. 					}
  119. 				}
  120.  
  121. 				boolean[] navstivene = new boolean[zoznam.size()];
  122. 				for(int i=0; i<zoznam.size(); ++i){
  123. 					zoznam.get(i).p=i;
  124. 					navstivene[i]=false;
  125. 				}
  126.  
  127. 				Vrch zac = new Vrch(0.0, zoznam.get(0), null);
  128. 				PriorityQueue<Vrch> fronta = new PriorityQueue<Vrch>();
  129. 				fronta.add(zac);
  130.  
  131. 				while(!fronta.isEmpty()){
  132. 					Vrch v = fronta.poll();
  133. 					//System.out.println(v.v + " " + v.d);
  134. 					if(navstivene[v.v.p]) continue;
  135. 					if(v.v.p==1) {
  136. 						System.out.println(v.d);
  137. 						break;
  138. 					}
  139. 					navstivene[v.v.p] = true;
  140. 					for(Vrchol sus: v.v.sused){
  141. 						double vz = v.d + v.v.vzdialenost(sus)/S;
  142. 						if(v.p!=null) vz += uhol(v.p, v.v, sus)/T;
  143. 						Vrch s = new Vrch(vz, sus, v.v);
  144. 						fronta.add(s);
  145. 					}
  146. 				}
  147.  
  148. 				//System.out.println(zoznam.size());
  149.  
  150. 			} catch (Exception e) {
  151. 				e.printStackTrace();
  152. 				return;		
  153. 			}
  154. 		}
  155. 	}
  156. }
  157.  

Diff to submission s1227

Cockchaf.java

--- c4.s1227.cteam131.cockchaf.java.0.Cockchaf.java
+++ c4.s1330.cteam131.cockchaf.java.0.Cockchaf.java
@@ -69,5 +69,5 @@
                 int dz2 = v3.z-v2.z;
                 
-                return (Math.acos(Math.abs(dx1*dx2 + dy1*dy2 + dz1*dz2) / (Math.sqrt(a2(dx1)+a2(dy1)+a2(dz1)) * Math.sqrt(a2(dx2)+a2(dy2)+a2(dz2))))/Math.PI*180);              
+                return (Math.acos((dx1*dx2 + dy1*dy2 + dz1*dz2) / (Math.sqrt(a2(dx1)+a2(dy1)+a2(dz1)) * Math.sqrt(a2(dx2)+a2(dy2)+a2(dz2))))/Math.PI*180);              
         }