Skip to content

Instantly share code, notes, and snippets.

@Nucleareal
Created May 14, 2013 14:13
Show Gist options
  • Save Nucleareal/5576222 to your computer and use it in GitHub Desktop.
Save Nucleareal/5576222 to your computer and use it in GitHub Desktop.
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main
{
public static void main(String[] args)
{
Scanner scn = new Scanner(System.in);
int Num = 0;
while((Num = Integer.valueOf(scn.nextLine())) != 0)
{
double[][] circles = new double[Num][2];
for(int i = 0; i < Num; i++)
{
String s = scn.nextLine();
StringTokenizer sz = new StringTokenizer(s, ",");
circles[i][0] = Double.valueOf(sz.nextToken());
circles[i][1] = Double.valueOf(sz.nextToken());
}
int count = 1, max = 1;
for(int i = 0; i < Num; i++)
{
for(int j = i+1; j < Num; j++)
{
if(!colCheck(circles[i][0], circles[i][1], circles[j][0], circles[j][1])) continue;
count = 2;
double dx = (circles[i][0] + circles[j][0]) / 2D;
double dy = (circles[i][1] + circles[j][1]) / 2D;
for(int k = 0; k < Num; k++)
{
if(k == i || j == k) continue;
if(colCheck(dx, dy, circles[k][0], circles[k][1]))
{
count++;
}
}
if(count > max)
{
//System.out.printf("(%f, %f): %d -> %d\n", dx, dy, max, count);
max = count;
}
}
}
System.out.println(max);
}
}
public static boolean colCheck(double dx, double dy, double px, double py)
{
double ddx = dx - px;
double ddy = dy - py;
return Math.sqrt(ddx*ddx+ddy*ddy) <= 2D;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment