欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定2D平面上的n个点,找到位于同一直线上的最大点数

程序员文章站 2022-04-01 18:41:46
...

本题源自LeetCode

--------------------------------------------------------

二重遍历,第一次遍历确定一个点a,在遍历剩下的点b.分三种情况 1 a,b 重合 2 a,b 垂直 3 ,a,b是一条b/a 的直线。

   int maxPoints(vector<Point> &points) {
        int length=points.size();
        if(length==0)
            return 0;
        if(length==1)
            return 1;
        int ret=0;
        for(int i=0;i<length;i++){
            int currentMax=1;
            int dup=0;    //记录重复点
            int vcnt=0;   //记录垂直点
            map<double,int> linemap;  //键为斜率
            for(int j=i+1;j<length;j++){
                //必须定义为double 因为要计算斜率
                double x=points[i].x-points[j].x;  
                double y=points[i].y-points[j].y;
                if(x==0&&y==0){     //重复
                    dup++;
                }else if(x==0){   //垂直
                    if(vcnt==0)
                        vcnt=2;
                    else
                        vcnt++;
                    currentMax=max(currentMax,vcnt);
                }else{            //斜率
                    double k=y/x;
                    if(linemap[k]==0)
                        linemap[k]=2;
                    else 
                        linemap[k]++;
                    currentMax=max(currentMax,linemap[k]);
                }
            }
            ret=max(currentMax+dup,ret);
        }
        return ret;
    }