import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; /** * */ /** * Sample solution for Collision Detection * * @author zeil * */ public class CollisionDetection_zeil { private Scanner input; public CollisionDetection_zeil(Scanner in) { input = in; } /** * @param args * @throws IOException */ public static void main (String[] argv) throws IOException { BufferedReader in; if (argv.length > 0) { in = new BufferedReader(new FileReader(argv[0])); } else { in = new BufferedReader (new InputStreamReader(System.in)); } run (in); } final static void run (BufferedReader bin) { Scanner in = new Scanner(bin); boolean done = false; while (!done) { CollisionDetection_zeil problem = new CollisionDetection_zeil(in); done = problem.solve(); } } class Observation { public double t, x, y, s; public Observation (Scanner in) { t = in.nextDouble(); x = in.nextDouble(); y = in.nextDouble(); s = in.nextDouble(); } } static final double SpeedLimit = 80.0; class Car { // Info about the car during the first phase of its movement // when it is accelerating (or decelerating) public double a0; public double s0; public double x0; public double y0; public double t0; public double dx; public double dy; public double d1; public double t1; // time at which acceleration ends // Info about the car at time t1 public double s1; public double x1; public double y1; public Car (Observation o1, Observation o2) { Observation older; Observation newer; if (o1.t < o2.t) { older = o1; newer = o2; } else { older = o2; newer = o1; } dx = newer.x - older.x; dy = newer.y - older.y; d1 = Math.sqrt(dx * dx + dy*dy); t0 = newer.t; s0 = newer.s; x0 = newer.x; y0 = newer.y; a0 = (newer.s - older.s) / (newer.t - older.t); if (a0 > 0.0) { // car is accelerating t1 = t0 + (SpeedLimit - s0) / a0; s1 = SpeedLimit; } else if (a0 < 0.0){ // car is decelerating t1 = t0 - s0 / a0; s1 = 0.0; } else { t1 = t0+1; s1 = s0; } x1 = x(t1); y1 = y(t1); } public double x(double t) { if (d1 == 0.0) return x0; if (t > t1) { double dt = t - t1; double d = s1 * dt; d = d * dx / d1; return x1 + d; } else { double dt = t - t0; double d = a0 * dt * dt / 2.0 + s0 * dt; d = d * dx / d1; return x0 + d; } } public double y(double t) { if (d1 == 0.0) return y0; if (t > t1) { double dt = t - t1; double d = s1 * dt; d = d * dy / d1; return y1 + d; } else { double dt = t - t0; double d = a0 * dt * dt / 2.0 + s0 * dt; d = d * dy / d1; return y0 + d; } } } public Car car1, car2; private boolean solve() { Observation o1 = new Observation(input); if (o1.t < 0.0) return true; Observation o2 = new Observation(input); car1 = new Car(o1, o2); Observation o3 = new Observation(input); Observation o4 = new Observation(input); car2 = new Car(o3, o4); double deltaT = 5.0 / 160.0; // time for two cars heading straight // towards one another at top speed to reduce gap by 5.0 ft. double t0 = Math.max(Math.max(o1.t, o2.t), Math.max(o3.t, o4.t)); double dt = 0.0; boolean dangerous = false; double minD = Double.MAX_VALUE; double minT = 0.0; while (dt < 30.0 + deltaT /*&& !dangerous*/) { double t = t0 + Math.min(dt, 30.0); double x1 = car1.x(t); double y1 = car1.y(t); double x2 = car2.x(t); double y2 = car2.y(t); double dx = x1 - x2; double dy = y1 - y2; double d = Math.sqrt(dx*dx + dy * dy); if (d < minD) { minD = d; minT = t; } dangerous = dangerous || d < 18.0; // in contest I would use 19.0 dt += deltaT; } if (dangerous) { System.out.println ("Dangerous"); } else { System.out.println ("Safe"); } //System.out.println ("(Min Distance occurred at t=" + minT + " and was " + minD + ")"); return false; } }