lintcode Max Points on a Line-蒲公英云

lintcode Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Have you met this question in a real interview?

Yes

Example

Given 4 points: (1,2), (3,6), (0,0), (1,3).

The maximum number is 3.

Tags

package tju.cs.bigdata;
import java.util.HashSet;
import java.util.Set;
public class MaxPointsonaLine {
    /**
     * @param points an array of point
     * @return an integer
     * </br>ac
     */
    public int maxPoints(Point[] points) {
        // Write your code here
        int res = 0;
        if(points == null) return res;
        // points = delSame(points);
        int len = points.length;
        if(len < 3) return len;
        int samecount = 0;
        for(int i = 0 ; i < len; i++){
            int tmps = 1;
            for(int j = 0; j < len; j++){
                if(i == j)continue;
                if(points[i].x == points[j].x && points[i].y == points[j].y){
                    tmps++;
                    continue;
                }
                int tmpc = 2;
                for(int k = 0 ;k < len; k++){
                    if(k == i || k == j){
                        continue;
                    }
                    if(isOnLine(points[i] , points[j] , points[k])){
                        tmpc++;
                    }    
                }
                if(tmpc > res)res = tmpc;
            }
            if(tmps > samecount)samecount = tmps;
        }
        return Math.max(samecount,res);
    }
       /**
     * @param points an array of point
     * @return an integer
     * 思路錯誤
     */
    public int maxPoints1(Point[] points) {
        // Write your code here
        int res = 0;
        if(points == null) return res;
        int len = points.length;
        if(len < 3) return len;
        for(int i = 0 ; i < len-1; i++){
            int tmpc = 2;
            for(int j = 0; j < len; j++){
                if(j == i || j == i + 1){
                    continue;
                }
                if(isOnLine(points[i] , points[i+1] , points[j])){
                    tmpc++;
                }
            }
            if(tmpc > res)res = tmpc;
        }
        return res;
    }
    public boolean isOnLine(Point a, Point b, Point c){
        int left = (a.x - b.x)*(c.y - b.y);
        int right = (a.y - b.y)*(c.x - b.x);
        if(left == right){
            return true;
        }else{
            return false;
        }
    }
    public static void main(String[] args){
//        String string = "[[0,9],[138,429],[115,359],[115,359],[-30,-102],[230,709],[-150,-686],[-135,-613],[-60,-248],[-161,-481],[207,639],[23,79],[-230,-691],[-115,-341],[92,289],[60,336],[-105,-467],[135,701],[-90,-394],[-184,-551],[150,774]]";
        String string = "[[0,-12],[5,2],[2,5],[0,-5],[1,5],[2,-2],[5,-4],[3,4],[-2,4],[-1,4],[0,-5],[0,-8],[-2,-1],[0,-11],[0,-9]]";
        System.out.println(string);
        String[] stes = string.split("],\\[");
        int steslen = stes.length; 
        stes[0] = stes[0].substring(2, stes[0].length());
        stes[steslen - 1] = stes[steslen - 1].substring(0, stes[steslen - 1].length() - 2);
        Set<Point> setpoints = new HashSet<>();
        for(int i = 0 ; i < stes.length; i ++){
            System.out.println(stes[i] + " ");
            int x = Integer.parseInt(stes[i].split(",")[0]);
            int y = Integer.parseInt(stes[i].split(",")[1]);
            setpoints.add(new Point(x,y));
        }
        Point[] points = setpoints.toArray(new Point[setpoints.size()]);
        System.out.println("最大的：" + new MaxPointsonaLine().maxPoints(points));
    }
}