- //@Nomad1
- import java.io.*;
- import java.util.*;
- public class Contest
- {
- static final int SEGMENT_LENGTH = 10000000;
- static final int BUFFER_LENGTH = 50000;
- static final double LIGHT_SPEED_COEF = 29.9792458; // Nomad: 299792458/10000000, divide by receiving speed 10M/s and multiply by light speed
- static final double MAX_DISTANCE_EPSILON = 100; // allowed distance larger than satellite raidus
- static final double MIN_DISTANCE_EPSILON = -1000; // allowed distance smaller than satellite raidus
- static final double EARTH_RADIUS = 6378000;
- /// Nomad1: parsing double value from byte stream, nothing special here except line feed processing
- static double readFloat(InputStream stream) throws IOException
- {
- char [] data = new char[20]; // Gates: 20 bytes should be enough for everyone!
- int offset = 0;
- do
- {
- int b = stream.read();
- if (b == '\r' || b == '\n')
- {
- if (offset != 0)
- break;
- } else
- {
- data[offset] = (char)b;
- offset ++;
- }
- } while(offset < data.length);
- // 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
- return Double.parseDouble(new String(data));
- }
- static double processSatellite(InputStream stream) throws IOException
- {
- int offset = 0;
- byte [] buffer = new byte[BUFFER_LENGTH];
- int left = SEGMENT_LENGTH;
- int countOne = 0;
- int countZero = 0;
- int phaseShift = -1;
- int dataOffset = 0;
- while(left > 0)
- {
- int read = stream.read(buffer, 0, left > BUFFER_LENGTH ? BUFFER_LENGTH : left);
- left -= read;
- if (phaseShift == -1)
- {
- byte last = -1;
- for(int i = 0; i < 200; i++)
- {
- byte bit = buffer[i];
- if (bit != '0' && bit != '1')
- {
- dataOffset++;
- continue;
- }
- if (bit != last && last != -1)
- {
- phaseShift = -dataOffset + (i % 10);
- //System.out.println("Phase shift " + phaseShift + ", data offset " + dataOffset + ", i " + i);
- break;
- }
- last = bit;
- }
- }
- int j = dataOffset; // Nomad: do not start from the first symbol because it can be '\r' or '\n' from incorrectly cut string
- while(j < read && countOne < 18 && countZero < 18)
- {
- byte bit = buffer[j];
- j += 10; // Nomad: sometimes it can lead to missing one step if read % 10 != 0. DON'T do something like this in real environment
- if (bit == '0')
- {
- countOne = 0;
- countZero++;
- } else
- {
- countOne++;
- countZero = 0;
- }
- }
- if (countZero >= 18)
- {
- offset = -read + j - countZero * 10 - 427401;
- break;
- }
- if (countOne >= 18)
- {
- offset = -read + j - countOne * 10 - 6375481;
- break;
- }
- }
- if (phaseShift != 0)
- offset += -10 + phaseShift;
- offset += SEGMENT_LENGTH - left;
- stream.skip(left + 1);
- // Nomad: I don't want to skip both '\r' and '\n' here at all - readFloat will handle this or even stream would end.
- return offset * LIGHT_SPEED_COEF;
- }
- static void circleIntersection(double[] one, double [] another, List<double[]> points)
- {
- double e = another[0] - one[0]; // [difference in x coordinates]
- double f = another[1] - one[1]; // [difference in y coordinates]
- double p = Math.sqrt(e*e + f*f); // [distance between centers]
- if (p == 0)
- return;
- 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]
- double h = Math.sqrt(one[2]*one[2] - k*k)/p; // vector from joining line to one of intersection points divided
- double centerx = one[0] + e*k/p;
- double centery = one[1] + f*k/p;
- if (h == 0)
- points.add(new double[]{ centerx, centery });
- else
- {
- points.add(new double[]{ centerx + f * h, centery - e * h });
- points.add(new double[]{ centerx - f * h, centery + e * h });
- }
- }
- static boolean validPoint(double[][] satellites, double [] point)
- {
- for(int i=0;i<satellites.length;i++)
- {
- double x = satellites[i][0] - point[0];
- double y = satellites[i][1] - point[1];
- double dist = Math.sqrt(x*x + y*y) - satellites[i][2];
- if (dist > MAX_DISTANCE_EPSILON || (i != 0 && dist < MIN_DISTANCE_EPSILON))
- {
- //System.out.println("Point " + point[0] + ", " + point[1] + " does not lies in circle#" + i + ", diff " + dist);
- return false;
- }
- }
- return true;
- }
- static void findPoints(double[][] satellites, List<double[]> points)
- {
- for (int i = 0; i < satellites.length; i++)
- for (int j = i + 1; j < satellites.length; j++)
- circleIntersection(satellites[i], satellites[j], points);
- //System.out.println("Got " + points.size() + " pts");
- double x = 0, y = 0;
- for (int i = 0; i < points.size(); i++)
- {
- double[] point = points.get(i);
- if (!validPoint(satellites, point))
- {
- points.remove(i);
- i--;
- } else
- {
- x += point[0];
- y += point[1];
- }
- }
- x /= points.size();
- y /= points.size();
- //System.out.println("After cleanup got " + points.size() + " points");
- System.out.println((float) x + " " + (float) y);
- }
- public static void main(String [] args)
- {
- //long time = System.nanoTime();
- try
- {
- InputStream stream = System.in;
- int nsatellites = (int)readFloat(stream);
- double[][] satellites = new double[nsatellites + 1][];
- satellites[0] = new double[]{0,0,EARTH_RADIUS,EARTH_RADIUS*EARTH_RADIUS};
- List<double[]> points = new ArrayList<double[]>();
- for(int i=1;i<nsatellites+1;i++)
- {
- double x = readFloat(stream);
- double y = readFloat(stream);
- double distance = processSatellite(stream);
- //System.out.println("Sat[" + i + "]: " + x + ", " + y + ", distance " + distance);
- satellites[i] = new double[]{x, y, distance};
- }
- findPoints(satellites, points);
- }
- catch (Exception e)
- {
- e.printStackTrace();
- }
- //System.out.println("Elapsed time: " + (System.nanoTime() - time) / 1000000.0);
- }
- }