Problem: Given a two-dimensional graph with points on it, find a line which passes the most number of points.
此题是Cracking the code 5th edition 第七章第六题，思路就是 n choose 2, 所以时间复杂度是O(n^2)，因为没有更快的办法。
此题的难点在于两点一线计算出的斜率是浮点型，不好比较equality。所以其中需要有一个精确到哪一位的概念，英文是 round to a given place value.
我认为此题书中给的解法特别傻逼，而且时间复杂度也超出了O(n^2)，故自己写了一个更好的版本。
另，关于使用自定义类用作HashMap的键值，如何重写equals()和hashCode()，下面的代码给出的很好的示范。
package chapter7; import java.util.HashMap; // given a two-dimensional graph with points on it,
// find a line which passes the most number of points
// Time: O(N^2), N is number of points // The tricky part is checking the equality of slope
// which is of type double.
// My solution is floor all values to an epsilon value
// which specifies the desired precision public class P6 { public Line findBestLine(GraphPoint[] points){
Line bestLine = null;
int bestCount = 0;
HashMap<Line, Integer> lineCounts =
new HashMap<Line, Integer>(); for(int i = 0; i < points.length; ++i){
for(int j = i+1; j < points.length; ++j){
Line line = new Line(points[i], points[j]);
int currentCount; if(lineCounts.containsKey(line)){
currentCount = lineCounts.get(line) + 1;
}else{
currentCount = 1;
}
lineCounts.put(line, currentCount); if(currentCount > bestCount){
bestCount = currentCount;
bestLine = line;
}
}
} return bestLine;
}
} class Line{
// for precision
// slope and intercept values are floored to epsilon
public static double epsilon = .0001; // properties for a normal line
public double slope;
public double y_intercept; // properties for a verticle line
public boolean infinite_slope = false;
public double x_intercept; public Line(GraphPoint p1, GraphPoint p2){ if(p1.x == p2.x){
this.infinite_slope = true;
this.x_intercept = p1.x; }else{
this.slope = (p1.y - p2.y) / (p1.x - p2.x);
this.y_intercept = p1.y - slope * p1.x; } // floor all properties
this.slope = floor(this.slope);
this.x_intercept = floor(this.x_intercept);
this.y_intercept = floor(this.y_intercept);
} public double floor(double val){
int val2 = (int)(val / epsilon);
return val2 * epsilon;
} @Override
public int hashCode(){
if(infinite_slope){
return (int) x_intercept;
}else{
return (int) (slope + y_intercept);
}
} @Override
public boolean equals(Object obj){
if(this == obj)
return true;
if(obj == null)
return false;
if(getClass() != obj.getClass())
return false; Line other = (Line)obj; if(infinite_slope && other.infinite_slope){ // both true
return x_intercept == other.x_intercept; }else if(infinite_slope || other.infinite_slope){ // one true, one false
return false;
}
else{ // both false
return slope == other.slope && y_intercept == other.y_intercept;
}
}
} class GraphPoint{
// assume that x and y are both floored
// to some point
public double x;
public double y;
}