Given a two-dimensional graph with points on it, find a line which passes the most number of points.

CC150-7.6.java

package POJ;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;

public class Main{
 
	/**
	 * 
	 * 7.6	Given a two-dimensional graph with points on it, find a line which passes the most number of points.
	 * 
	 * Solution:
	 * 感觉挺繁杂的一道题，leetcode上也有一道类似的题，最主要需要关注的问题就是double类型值的处理。
	 * 
	 */
//	public static void main(String[] args) {
//		Main so = new Main();
//		
//	}

	public Line findBestLine(Point[] points) {
		Line bestLine = null;
		int bestCount = 0;

		HashMap<Double, ArrayList<Line>> linesBySlope = new HashMap<Double, ArrayList<Line>>();

		for (int i = 0; i < points.length; i++) {
			for (int j = i; j < points.length; j++) {
				Line line = new Line(points[i], points[j]);
				insertLine(linesBySlope, line);
				int count = countEquivalentLines(linesBySlope, line);
				if (count > bestCount) {
					bestCount = count;
					bestLine = line;
				}

			}
		}
		return bestLine;
	}

	private int countEquivalentLines(
			HashMap<Double, ArrayList<Line>> linesBySlope, Line line) {
		// TODO Auto-generated method stub
		double key = Line.floorToNeareastEpsilon(line.slope);
		double eps = Line.epsilon;
		int count = countEquivalentLines(linesBySlope.get(key), line)
				+ countEquivalentLines(linesBySlope.get(key - eps), line)
				+ countEquivalentLines(linesBySlope.get(key + eps), line);
		return count;
	}

	private int countEquivalentLines(ArrayList<Line> lines, Line line) {
		// TODO Auto-generated method stub
		if (lines == null)
			return 0;
		int count = 0;
		for (Line parallelLine : lines) {
			if (parallelLine.isEquivalent(line))
				count++;
		}
		return count;
	}

	private void insertLine(HashMap<Double, ArrayList<Line>> linesBySlope,
			Line line) {
		// TODO Auto-generated method stub
		ArrayList<Line> lines = null;
		double key = Line.floorToNeareastEpsilon(line.slope);
		if (!linesBySlope.containsKey(key)) {
			lines = new ArrayList<Line>();
			linesBySlope.put(key, lines);
		} else {
			lines = linesBySlope.get(key);
		}
		lines.add(line);
	}
}

class Line {
	public static double epsilon = 0.00001;
	public double slope, intersect;
	private boolean infinite_slope = false;

	public Line(Point p, Point q) {
		if (Math.abs(p.x - q.x) > epsilon) {
			slope = (p.y - q.y) / (p.x - q.x);
			intersect = p.y - slope * p.x; // y=mx+b
		} else {
			infinite_slope = true;
			slope = Integer.MAX_VALUE;
			intersect = p.x; // x-intersect, since slope is infinite
		}
	}

	public boolean isEquivalent(Line line) {
		// TODO Auto-generated method stub
		if (isEquivalent(line.slope, slope)
				&& isEquivalent(line.intersect, intersect)
				&& (line.infinite_slope == infinite_slope))
			return true;
		return false;
	}

	private boolean isEquivalent(double a, double b) {
		// TODO Auto-generated method stub
		return Math.abs(a - b) < epsilon;
	}

	public static double floorToNeareastEpsilon(double p) {
		int r = (int) (p / epsilon);
		return ((double) r) * epsilon;
	}
}