1. //@Nomad1
  2. import java.io.*;
  3. import java.util.*;
  4. public class Contest
  5. {
  6. static final int SEGMENT_LENGTH = 10000000;
  7. static final int BUFFER_LENGTH = 50000;
  8. static final double LIGHT_SPEED_COEF = 29.9792458; // Nomad: 299792458/10000000, divide by receiving speed 10M/s and multiply by light speed
  9. static final double MAX_DISTANCE_EPSILON = 100; // allowed distance larger than satellite raidus
  10. static final double MIN_DISTANCE_EPSILON = -1000; // allowed distance smaller than satellite raidus
  11. static final double EARTH_RADIUS = 6378000;
  12. /// Nomad1: parsing double value from byte stream, nothing special here except line feed processing
  13. static double readFloat(InputStream stream) throws IOException
  14. {
  15. char [] data = new char[20]; // Gates: 20 bytes should be enough for everyone!
  16. int offset = 0;
  17. do
  18. {
  19. int b = stream.read();
  20. if (b == '\r' || b == '\n')
  21. {
  22. if (offset != 0)
  23. break;
  24. } else
  25. {
  26. data[offset] = (char)b;
  27. offset ++;
  28. }
  29. } while(offset < data.length);
  30. // Nomad: I do not cut both of '\r' and '\n' symbols here to save some processing time. To handle the issue with data string starting with this character I'll make 2-byte shift later
  31. return Double.parseDouble(new String(data));
  32. }
  33. static double processSatellite(InputStream stream) throws IOException
  34. {
  35. int offset = 0;
  36. byte [] buffer = new byte[BUFFER_LENGTH];
  37. int left = SEGMENT_LENGTH;
  38. int countOne = 0;
  39. int countZero = 0;
  40. int phaseShift = -1;
  41. int dataOffset = 0;
  42. while(left > 0)
  43. {
  44. int read = stream.read(buffer, 0, left > BUFFER_LENGTH ? BUFFER_LENGTH : left);
  45. left -= read;
  46. if (phaseShift == -1)
  47. {
  48. byte last = -1;
  49. for(int i = 0; i < 200; i++)
  50. {
  51. byte bit = buffer[i];
  52. if (bit != '0' && bit != '1')
  53. {
  54. dataOffset++;
  55. continue;
  56. }
  57. if (bit != last && last != -1)
  58. {
  59. phaseShift = -dataOffset + (i % 10);
  60. //System.out.println("Phase shift " + phaseShift + ", data offset " + dataOffset + ", i " + i);
  61. break;
  62. }
  63. last = bit;
  64. }
  65. }
  66. int j = dataOffset; // Nomad: do not start from the first symbol because it can be '\r' or '\n' from incorrectly cut string
  67. while(j < read && countOne < 18 && countZero < 18)
  68. {
  69. byte bit = buffer[j];
  70. j += 10; // Nomad: sometimes it can lead to missing one step if read % 10 != 0. DON'T do something like this in real environment
  71. if (bit == '0')
  72. {
  73. countOne = 0;
  74. countZero++;
  75. } else
  76. {
  77. countOne++;
  78. countZero = 0;
  79. }
  80. }
  81. if (countZero >= 18)
  82. {
  83. offset = -read + j - countZero * 10 - 427401;
  84. break;
  85. }
  86. if (countOne >= 18)
  87. {
  88. offset = -read + j - countOne * 10 - 6375481;
  89. break;
  90. }
  91. }
  92. if (phaseShift != 0)
  93. offset += -10 + phaseShift;
  94. offset += SEGMENT_LENGTH - left;
  95. stream.skip(left + 1);
  96. // Nomad: I don't want to skip both '\r' and '\n' here at all - readFloat will handle this or even stream would end.
  97. return offset * LIGHT_SPEED_COEF;
  98. }
  99. static void circleIntersection(double[] one, double [] another, List<double[]> points)
  100. {
  101. double e = another[0] - one[0]; // [difference in x coordinates]
  102. double f = another[1] - one[1]; // [difference in y coordinates]
  103. double p = Math.sqrt(e*e + f*f); // [distance between centers]
  104. if (p == 0)
  105. return;
  106. double k = p*0.5 + 0.5*(one[2]*one[2] - another[2]*another[2])/p; // [distance from center 1 to line joining points of intersection]
  107. double h = Math.sqrt(one[2]*one[2] - k*k)/p; // vector from joining line to one of intersection points divided
  108. double centerx = one[0] + e*k/p;
  109. double centery = one[1] + f*k/p;
  110. if (h == 0)
  111. points.add(new double[]{ centerx, centery });
  112. else
  113. {
  114. points.add(new double[]{ centerx + f * h, centery - e * h });
  115. points.add(new double[]{ centerx - f * h, centery + e * h });
  116. }
  117. }
  118. static boolean validPoint(double[][] satellites, double [] point)
  119. {
  120. for(int i=0;i<satellites.length;i++)
  121. {
  122. double x = satellites[i][0] - point[0];
  123. double y = satellites[i][1] - point[1];
  124. double dist = Math.sqrt(x*x + y*y) - satellites[i][2];
  125. if (dist > MAX_DISTANCE_EPSILON || (i != 0 && dist < MIN_DISTANCE_EPSILON))
  126. {
  127. //System.out.println("Point " + point[0] + ", " + point[1] + " does not lies in circle#" + i + ", diff " + dist);
  128. return false;
  129. }
  130. }
  131. return true;
  132. }
  133. static void findPoints(double[][] satellites, List<double[]> points)
  134. {
  135. for (int i = 0; i < satellites.length; i++)
  136. for (int j = i + 1; j < satellites.length; j++)
  137. circleIntersection(satellites[i], satellites[j], points);
  138. //System.out.println("Got " + points.size() + " pts");
  139. double x = 0, y = 0;
  140. for (int i = 0; i < points.size(); i++)
  141. {
  142. double[] point = points.get(i);
  143. if (!validPoint(satellites, point))
  144. {
  145. points.remove(i);
  146. i--;
  147. } else
  148. {
  149. x += point[0];
  150. y += point[1];
  151. }
  152. }
  153. x /= points.size();
  154. y /= points.size();
  155. //System.out.println("After cleanup got " + points.size() + " points");
  156. System.out.println((float) x + " " + (float) y);
  157. }
  158. public static void main(String [] args)
  159. {
  160. //long time = System.nanoTime();
  161. try
  162. {
  163. InputStream stream = System.in;
  164. int nsatellites = (int)readFloat(stream);
  165. double[][] satellites = new double[nsatellites + 1][];
  166. satellites[0] = new double[]{0,0,EARTH_RADIUS,EARTH_RADIUS*EARTH_RADIUS};
  167. List<double[]> points = new ArrayList<double[]>();
  168. for(int i=1;i<nsatellites+1;i++)
  169. {
  170. double x = readFloat(stream);
  171. double y = readFloat(stream);
  172. double distance = processSatellite(stream);
  173. //System.out.println("Sat[" + i + "]: " + x + ", " + y + ", distance " + distance);
  174. satellites[i] = new double[]{x, y, distance};
  175. }
  176. findPoints(satellites, points);
  177. }
  178. catch (Exception e)
  179. {
  180. e.printStackTrace();
  181. }
  182. //System.out.println("Elapsed time: " + (System.nanoTime() - time) / 1000000.0);
  183. }
  184. }