Java Codes by Gamer
Sunday, September 05, 2004
 
Google Code Jam 2004 Practice Room 250 Point
Problem Statement

There are often a number of cell towers that are within range of a cell phone. Your task is to find the best cell tower for a cell phone at a particular location. You will be given a String[], towers, each of whose elements is formatted as (quotes for clarity) "(,)", where and are decimal numbers. You will also be given two ints, x and y, representing the location of the cell phone. Your method should return the index of the best cell tower, where best is defined as follows. First, you should find the distance to the closest cell tower, and then you should find all of the towers that are at most 2 units farther out than that one. Of these, you should return the index (starting from 0) of the one with the lowest index. The idea behind this is that the towers have already been ranked, with lower indexed towers being better in some way, so if one of the lower indexed towers is almost the closest, it would be preferable to use it over the true closest. 






import java.util.*;



public class CellTower

{

	public static void main(String args[])

	{

		

		String[] param0 = {"(-43.54,632.5331)","(43.53,632.5332)","(-652.23000,00.000)"};

		int param1 = 30;

		int param2 = 532;

		

		int result;



		result = best(param0,param1,param2);

		

		System.out.println( result );



	}





	public static int best(String[] towers, int x, int y)

	{

		Point []points = new Point[ towers.length ];

		

		StringTokenizer st;

		for( int i = 0; i < towers.length; i++ )

		{

			points[i] = new Point();

			

			st = new StringTokenizer( towers[i], "(),");

			

			points[i].x = Float.parseFloat( st.nextToken() );

			points[i].y = Float.parseFloat( st.nextToken() );

			

		}

		

		Point myp = new Point();

		

		myp.x = x;

		myp.y = y;

		

		//now distance from every point

		

		float dis[] = new float[ towers.length ];

		

		for( int i = 0; i < towers.length; i++ )

		{

			dis[i] = (float)Math.sqrt( (( points[i].x - myp.x ) * ( 
                             points[i].x - myp.x )) + (( points[i].y - myp.y ) * 
                             ( points[i].y - myp.y )) );

		}

		

		float dis2[] = new float[ towers.length ];

		

		for( int i = 0; i < dis.length; i++ )

		{

			dis2[i] = dis[i];

		}

		

		Arrays.sort( dis2 );

		

		int ans = 0;

		for( int i = 0; i < dis.length; i++ )

		{

			if( dis2[0] == dis[i] )

			{

				ans = i;

				break;

			}

		}

		

		for( int i = 0; i < dis.length; i++ )

		{

			if( dis[i] <= dis[ans] + 2 )

			{

				ans = i;

				break;

			}

		}

		

		

		return ans;

	}

}



class Point

{

	float x;

	float y;

}



- posted by Max @ 10:35 AM
Comments:
I would like to exchange links with your site www.blogger.com
Is this possible?
# posted by Anonymous Anonymous : August 1, 2010 at 2:45 PM
 
Post a Comment

<< Home

Powered by Blogger