import java.io.*; import java.util.*; /** * The Red Gem * @author vanb * * Consider a red and orange circle. Look at the two lines which * are tangent to both circles, which cross between the circles. * Think of them as rays, starting from the red circle and glancing * past the orange circle. These are sightlines, and between them, * the orange circle blocks at least part of the red circle. * So, project those rays all the way to the edge of the purple * circle, and keep track of the range of angles that are blocked. * Do this for all of the orange circles, and union the ranges. * That gives you all of the ranges on the edge of the purple circle * which *cannot* see all of the red gem. It's easy from there to * figure out the proportion that *can* see all of the red gem. */ public class redgem { public Scanner sc; public PrintStream ps; public static final double TWOPI = Math.PI+Math.PI; /** * Class to hold a range of angles along * the purple platform which are blocked from viewing * the red gem. * * @author vanb */ public class Range { // Low, High ends of the range double lo, hi; /** * Create a range * * @param l Low end of range * @param h High end of range */ public Range( double l, double h ) { lo=l; hi=h; } /** * Pretty printing for debugging * * @return Pretty range */ public String toString() { return "[" + lo + ".." + hi + "]"; } } public LinkedList ranges = new LinkedList(); public LinkedList temp = new LinkedList(); /** * Add a range to the list, merging it with any existing * ranges that it overlaps. * * @param lo Low end of new range * @param hi High end of new range */ public void addRange( double lo, double hi ) { // We'll build up a list of ranges in temp, // and then swap it with 'ranges' to make it the real list. temp.clear(); // Look at all of the existing ranges for( Range range : ranges ) { // If the range intersects this new one if( hi>=range.lo && range.hi>=lo ) { // Merge it into the new one lo = Math.min( lo, range.lo ); hi = Math.max( hi, range.hi ); } else { // Otherwise, just keep this one temp.add( range ); } } // Swap! LinkedList swap = ranges; ranges = temp; temp = swap; // Add this new range ranges.add( new Range( lo, hi ) ); } /** * Normalize an angle to be in the range from 0 to 2pi * * @param a Angle to normalize * @return Normalized angle */ public double normalize( double a ) { while( a<0 ) a += TWOPI; while( a>=TWOPI ) a -= TWOPI; return a; } /** * Given a ray shot from (x2,y2) through (x1,y1), determine the angle * of the point where that ray intersects a circle with center (0,0) * and radius r. * * @param x1 x1 of (x1,y1) * @param y1 y1 of (x1,y1) * @param x2 x2 of (x2,y2) * @param y2 y2 of (x2,y2) * @param r Radius of big circle * @return The desired angle */ public double getangle( double x1, double y1, double x2, double y2, double r ) { // Express the ray parametrically as x = px + qx*t, y = py + qy*t, t>=0 double px = x2; double qx = x1-x2; double py = y2; double qy = y1-y2; // We know that x^2 + y^2 = r^2. So, plug the parametric // equations in for x and y, and we get a quadratic in t. // It looks like this: // // (qx^2 + qy^2)*t^2 + 2*(px*qx + py*qy)*t + (px^2 + py^2 - r^2) = 0 // // Then we can just plug into the quadratic formula. double a = qx*qx + qy*qy; double b = 2.0*(px*qx + py*qy); double c = px*px + py*py - r*r; // That will give us t. We'll always take the larger value. // The smaller will be behind us, where t<0, since both points // are guaranteed to be inside the large purple circle. double t = (-b + Math.sqrt( b*b-4.0*a*c ))/(2.0*a); // That will give us the (x,y) point on the edge of the circle double x = px + qx*t; double y = py + qy*t; // And THAT will give us the angle we seek. return normalize( Math.atan2( y, x ) ); } /** * Do it! * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "redgem.in" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "redgem.out" ) ); for(int c=1;;++c) { int n = sc.nextInt(); // Purple radius (its center is always at (0,0) ) double pr = sc.nextDouble(); // The Red circle (x,y) center and radius double rx = sc.nextDouble(); double ry = sc.nextDouble(); double rr = sc.nextDouble(); if( n==0 ) break; ranges.clear(); for( int i=0; ifinish, then the range // spans the 0/2pi border. // No prob. We'll just add 2 ranges. addRange( start, TWOPI ); addRange( 0.0, finish ); } } // Now, compute a final answer. // Start with the whole thing visible, // remove the blocked ranges. double visible = TWOPI; for( Range range : ranges ) { visible -= (range.hi-range.lo); } ps.printf( "%.4f", visible/TWOPI ); ps.println(); // String result = String.format( "%.7f", visible/TWOPI ); // System.out.println( " " + result ); // if( result.endsWith( "500" ) || result.endsWith( "499" ) ) System.out.println( "PANIC!! Case " + c + " is too close to a cusp!" ); } } /** * Main * * @param args Unused * @throws Exception */ public static void main( String[] args ) throws Exception { new redgem().doit(); } }