1.
package acm_11227_the_silver_bullet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, WS10
* Problem: acm_11227_the_silver_bullet
* Link:
*
* @author Martin Lambeck
* @version 1.0, 23.10.2010
*
* Method : adhoc
* Status : Accepted
* Runtime: 0.600
*/
public class Main
{
static Scanner sc = new Scanner(System.in);
public static void main(String... args)
{
int cases = sc.nextInt();
for (int i = 0; i < cases; i++)
testcase(i+1);
}
public static void testcase(int tcase)
{
int n = sc.nextInt();
HashSet<Gnu> gnus = new HashSet<Gnu>(n+1);
for (int i = 0; i < n; i++)
{
gnus.add(new Gnu(sc.nextDouble(), sc.nextDouble()));
}
if (gnus.size() == 1)
{
System.out.printf("Data set #%d contains a single gnu.%n", tcase);
return;
}
ArrayList<Gnu> gnulst = new ArrayList<Gnu>(gnus);
int best = 0;
for (Gnu g : gnus)
{
int res = work(gnulst, g);
if (res > best)
best = res;
}
System.out.printf("Data set #%d contains %d gnus, out of which a maximum of %d are aligned.%n",
tcase, gnus.size(), best);
}
static int work(ArrayList<Gnu> gnus, Gnu zero)
{
for (Gnu g : gnus)
g.setAngle(zero);
Collections.sort(gnus);
double alpha = Double.NaN;
int row = 0;
int bestrow = 0;
for (Gnu g : gnus)
{
if (g == zero)
continue;
if (Math.abs(g.angle - alpha) <= 0.0000001)
{
row++;
} else
{
alpha = g.angle;
row = 2; //current (g) + zero
}
if (row > bestrow)
bestrow = row;
}
return bestrow;
}
}
class Gnu implements Comparable<Gnu>
{
double x = -1;
double y = -1;
double angle = -1;
public Gnu(double xx, double yy)
{
x = (xx == -0 ? 0 : xx);
y = (yy == -0 ? 0 : yy);
}
public void setAngle(Gnu zero)
{
angle = Math.atan2(x - zero.x, y - zero.y);
if (angle < 0)
angle += Math.PI;
}
public int compareTo(Gnu g)
{
if (angle == g.angle)
return 0;
return (angle < g.angle ? -1 : 1);
}
public int hashCode()
{
final int prime = 31;
int result = 1;
long temp;
temp = Double.doubleToLongBits(x);
result = prime * result + (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = prime * result + (int) (temp ^ (temp >>> 32));
return result;
}
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Gnu other = (Gnu) obj;
if (Double.doubleToLongBits(x) != Double.doubleToLongBits(other.x))
return false;
if (Double.doubleToLongBits(y) != Double.doubleToLongBits(other.y))
return false;
return true;
}
}