solved 'Max Points on a Line' on LeetCode (TRICK: use strings to represent lines!) http://oj.leetcode.com/problems/max-points-on-a-line/

MaxPoints.java

/*
reduced code from 120 lines to 40 lines:
    no need to build classes like Line and Fraction!
    it's enough to 
        1. represent lines using only slope since point i 
is fixed
        2. use string as the key of hashmap
*/

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length == 0) return 0;
        int result = 1;

        for (int i=0; i<points.length-result; ++i) {
            int duplicatePoint = 0, onePassMax = 1;
            // point i is fixed, only slope is necessary do differentiate lines
            Map<String, Integer> slopeCount = new HashMap<String, Integer>();
            for (int j=i+1; j<points.length; ++j) {
                int dy = points[i].y - points[j].y,
                    dx = points[i].x - points[j].x;
                if (dy == 0 && dx == 0) {// duplicate point
                    duplicatePoint++;
                    continue;
                }
                int abs_dy = java.lang.StrictMath.abs(dy),
                    abs_dx = java.lang.StrictMath.abs(dx);
                int g = gcd(abs_dy, abs_dx);
                String line =  (dy*dx<0 ? "-":"") + abs_dy/g + "/" + abs_dx/g;
                int num = 1;
                if (!slopeCount.containsKey(line))
                    slopeCount.put(line, 2);
                else {
                    num = slopeCount.get(line);
                    slopeCount.put(line, num+1);
                }
                if (num + 1 > onePassMax) onePassMax = num + 1;
            }
            if (onePassMax + duplicatePoint > result)
                result = onePassMax + duplicatePoint;
        }
        return result;
    }

    private int gcd(int x, int y) {
        if (y == 0) return x;
        else return (x < y) ? gcd(y, x) : gcd(y, x%y);
    }
}