Find the line through the most points
LineMostPoints.java
class Line {
private Pair<Integer, Integer> slope;
private Pair<Integer, Integer> intercept;
Line(Point a, Point b) {
if (a.x != b.x) {
slope = getCanonicalFractional(b.y - a.y, b.x - a.x);
} else {
slope = new Pair<>(1, 0);
}
if (a.x != b.x) {
intercept = getCanonicalFractional(b.x * a.y - a.x * b.y, b.x - a.x);
} else {
intercept = new Pair<>(a.x, 1);
}
}
public Pair<Integer, Integer> getSlope() {
return slope;
}
public Pair<Integer, Integer> getIntercept() {
return intercept;
}
@Override
public boolean equals(Object o) {
if (o instanceof Line) {
Line l = (Line) o;
return nullEqual(slope, l.getSlope())
&& nullEqual(intercept, l.getIntercept());
}
return false;
}
@Override
public int hashCode() {
return slope.getFirst() ^ slope.getSecond() ^ intercept.getFirst()
^ intercept.getSecond();
}
}
public class LineMostPoints {
private static int check(List<Point> P) {
int maxCount = 0;
for (int i = 0; i < P.size(); ++i) {
for (int j = i + 1; j < P.size(); ++j) {
int count = 2;
Line temp = new Line(P.get(i), P.get(j));
for (int k = j + 1; k < P.size(); ++k) {
if (new Line(P.get(i), P.get(k)).equals(temp)) {
++count;
}
}
maxCount = Math.max(maxCount, count);
}
}
return maxCount;
}
// @include
private static Line findLineWithMostPoints(List<Point> P) {
// Adds all possible lines into hash table.
Map<Line, Set<Point>> table = new HashMap<>();
for (int i = 0; i < P.size(); ++i) {
for (int j = i + 1; j < P.size(); ++j) {
Line l = new Line(P.get(i), P.get(j));
Set<Point> s1 = table.get(l);
if (s1 == null) {
s1 = new HashSet<>();
table.put(l, s1);
}
s1.add(P.get(i));
Set<Point> s2 = table.get(l);
if (s2 == null) {
s2 = new HashSet<>();
table.put(l, s2);
}
s2.add(P.get(j));
}
}
//@exclude
Set<Point> lineMaxPoints = Collections.max(table.values(),
new Comparator<Set<Point>>() {
@Override
public int compare(Set<Point> p1, Set<Point> p2) {
if (p1 != null && p2 != null) {
return new Integer(p1.size()).compareTo(p2.size());
} else if (p1 != null) {
return 1;
} else {
return -1;
}
}
}
);
int res = check(P);
assert (res == lineMaxPoints.size());
// Return the line with most points have passed.
//@include
return Collections.max(table.entrySet(),
new Comparator<Map.Entry<Line, Set<Point>>>() {
@Override
public int compare(Map.Entry<Line, Set<Point>> e1,
Map.Entry<Line, Set<Point>> e2) {
if (e1 != null && e2 != null) {
return new Integer(e1.getValue().size()).compareTo(e2.getValue()
.size());
} else if (e1 != null) {
return 1;
} else {
return -1;
}
}
}
).getKey();
}
