import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Coverage. * * Consider these two observations: * * If a 1km circle connects two other 1km circles, * then their centers must me inside a circle with 2km radius * * If a circle contains some points, then there is another circle * with the same radius, containing the same points, * with at least 2 of the points on the edge of the circle. * * That gives us our solution strategy. Pick pairs of points, form 2 2km circles, * and in turn, count points in each. We only need to consider points that are * within 4km of each other. * * @author vanb */ public class coverage_vanb { public Scanner sc; public PrintStream ps; /** * A Cell Tower. * * @author vanb */ public class Tower { /** Tower Location */ public double x, y; /** It's position in the list */ public int index; /** Which connected component it belongs to */ public int component = -1; /** A list of towers it's connected to (within 2km) */ public List edges = new LinkedList(); /** A list of candidate towers to be joined together by a new tower (within 4km) */ public List candidates = new LinkedList(); /** * Create a Tower * * @param index Position in list * @param x X coordinate * @param y Y coordinate */ public Tower( int index, double x, double y ) { this.index = index; this.x = x; this.y = y; } /** * Form connected components, and count. * * @param c ID of this connected component * @return Count of nodes */ public int countcomponent( int c ) { component = c; int count = 1; for( Tower tower : edges ) if( tower.component<0 ) { count += tower.countcomponent( c ); } return count; } } /** Number of nodes in each component */ public int sizes[]; /** Whether or not we've used a node from a given component */ public boolean used[]; /** The best answer we've found so far */ public int most; /** * Test a given circle, by counting the sizes of the components * of the towers inside of it. * * @param t Tower we're coming from * @param x X coordinate of circle center * @param y Y coordinate of circle center */ public void test( Tower t, double x, double y ) { // Well, we know that tower t's component is here. int towers = sizes[t.component]; used[t.component] = true; // Go through the candidates from this tower // that are from components we haven't used yet for( Tower t1 : t.candidates ) if( t1.index>t.index && !used[t1.component] ) { // If it's inside a 2km circle centered at (x,y) if( Math.hypot( t1.y-y, t1.x-x ) < 2.0000001 ) { // Then include its component used[t1.component] = true; towers += sizes[t1.component]; } } // Undo used[] used[t.component] = false; for( Tower t1 : t.candidates ) if( used[t1.component] ) used[t1.component] = false; // If this is the best we've found so far, remember it. if( towers>most ) most = towers; } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; // Read in the towers int n = sc.nextInt(); Tower towers[] = new Tower[n]; for( int i=0; imost ) most = sizes[c]; ++c; } // Got though each tower, and form a pair with each of its candidates. // From that pair, form 2 circles with 2km radius that go through both points. // For each of those circles, figure out the size of merged component // formed by all of the towers in that circle. for( Tower t1 : towers ) for( Tower t2 : t1.candidates ) if( t2.index>t1.index ) { // Distance between the towers double distance = Math.hypot( t2.y-t1.y, t2.x-t1.x ); // Angle between the towers double theta = Math.atan2( t2.y-t1.y, t2.x-t1.x ); // Angle to the center of the circle // // t1----------P----------t2 // \psi | / // \ | / // \ | / // \ | / // \ | / // C // // Let d = the distance |t1->t2| // Let P = midpoint of t1->t2. Then |t1->P| = d/2 // If C is the center of a circle, radius 2, and both t1 and t2 are on the edge, // then C-P-T1 is a right angle. So cos(psi) = |t1->P|/2 = d/2/2 = d/4 double psi = Math.acos( distance/4.0 ); // Test the 2 circles test( t1, t1.x + 2.0*Math.cos( theta+psi ), t1.y + 2.0*Math.sin( theta+psi ) ); test( t1, t1.x + 2.0*Math.cos( theta-psi ), t1.y + 2.0*Math.sin( theta-psi ) ); } // Print the best answer. // We've got to add 1 to account for the new tower that we're adding. ps.println( ++most ); } /** * @param args */ public static void main( String[] args ) throws Exception { new coverage_vanb().doit(); } }