import java.io.*; import java.util.*; import java.math.*; /** * Solution to Reconnaissance * * @author vanb */ public class recon_vanb { public Scanner sc; public PrintStream ps; /** * A Car, with initial position and velocity. * * @author vanb */ public class Car implements Comparable { /** Initial position */ public int x; /** Velocity */ public int v; /** * Create a Car. * * @param x Initial position * @param v Velocity */ public Car( int x, int v ) { this.x = x; this.v = v; } /** * Compare this car to another, so they can be sorted * first by velocity (largest first) and in case of ties, * then by initial position (smallest first). * * @param c Another Car * @return The norm for compareTo */ public int compareTo( Car c ) { int diff = c.v - v; if( diff==0 ) diff = x - c.x; return diff; } /** * Position of this Car at time t. * * @param t A Time * @return Position of this car at time t */ public double pos( double t ) { return x+v*t; } /** * Time when two cars intersect, or Max Double * if they don't intersect. * * @param c Another Car * @return Time of intersection, or Max Double if they don't intersect. */ public double intersect( Car c ) { // The only way they don't intersect is if they're traveling // at the same velocity. return v==c.v ? Double.MAX_VALUE : (x-c.x)/(double)(c.v-v); } /** * A pretty String for debugging. * * @return A pretty String for debugging */ public String toString() { return "[" + x + "," + v + "]"; } } /** * Class to capture a Switch in the leftmost (or rightmost) car * * @author vanb */ public class Switch { /** Time of the switch */ public double t; /** The Car that takes over as leftmost (or rightmost) at time t */ public Car c; /** * Capture a Switch. * * @param t Time of switch * @param c Car that becomes the leftmost (or rightmost) at time t */ public Switch( double t, Car c ) { this.t = t; this.c = c; } /** * A Pretty String for debugging * * @return A pretty String for debugging */ public String toString() { return "{" + t + "," + c + "}"; } } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "reconnaissance.sample" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "reconnaissance.out" ) ); // Create all of the arrays a priori to save time Car cars[] = new Car[100000]; Switch lswitches[] = new Switch[100001]; Switch rswitches[] = new Switch[100001]; for(;;) { int n = sc.nextInt(); if( n==0 ) break; for( int i=0; i= rx ) { rx = cars[c].x; rc = c; } } // Look for all the places where the leftmost car switches // (that is, where another car becomes the leftmost) Arrays.fill( lswitches, null ); int k = 0; lswitches[k++] = new Switch( 0.0, cars[lc] ); // We only need to look at cars that are slower (or going in the opposite direction). // That's easy, since the cars are sorted by velocity. for( int c=lc+1; c=0 ) { sw.t = cars[c].intersect( lswitches[i].c ); if( sw.t >= lswitches[i].t ) break; --i; } k=i+1; // This if() will only fail if the cars are moving at the same velocity, // so there is no intersection. if( sw.t=0; c-- ) { Switch sw = new Switch( 0.0, cars[c] ); int i = k-1; while( i>=0 ) { sw.t = cars[c].intersect( rswitches[i].c ); if( sw.t >= rswitches[i].t ) break; --i; } k=i+1; if( sw.t