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

max_points_on_a_line

程序员文章站 2022-06-02 22:13:46
...
/**
 * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */

首先想到的是 k=(y2-y1)/(x2-x1),先锁定两个点x1,x2确定一条直线,每次进来一个点就分别与x1,x2根据上式计算斜率,比较与原来的斜率是否相等,若是就把当前直线上点数加一,然后代码大概是这样

class Solution {
public:
    int maxPoints(vector<Point> &points) {

        int l=points.size();

        if(l==1)
        return 1;

        int max=0;

        for(int i=0;i<l-1;i++){

            for(int j=i+1;j<l;j++){
                int temp=2;
                float k=((float)points[i].y-(float)points[j].y)/(points[i].x-points[j].x);

                for(int t=j+1;t<l;t++){
                    cout<<points[i].x-points[t].x<<endl;
                    float kn=((float)points[i].y-(float)points[t].y)/(points[i].x-points[t].x);
                    //cout<<kn<<endl;
                //  float k1=((float)points[t].y-(float)points[i].y)*(points[j].x-points[i].x);
                //  float k2=((float)points[j].y-(float)points[i].y)*(points[t].x-points[i].x);
                    if(k==kn){
                        //cout<<kn<<endl;
                        temp+=1;}
                }

                max=max>temp?max:temp;
            }
        }

        return max;
    }
};

这么写存在的问题是首先会有除以0的情况(一条与y轴平行的线上的点),虽然把结果转成float保存,代码不会报错(float型有表示这类数的方法),但当点一样的时候,就会出问题了。

(0,0)
(1,1)
(0,0)

按照公式 (0,0)(1,11(斜率)  
        (0,0)(0,0nan(斜率)

结果是只有两个点(但是需要是3个点)。

遇到这种情况,立马想到是除以0导致的,于是决定换一个没有除以0的公式。

(x2-x1)(y3-y1)==(x3-x1)(y2-y1)

代码与上一个类似。
但是,又有新的问题

测试用例:
[(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)]

对应输出应该为:

12

你的输出为:

19

当时想不太明白为什么会多算点,而且输入看上去有点复杂,于是画了图寻找这一个输入序列的特殊之处,但是没有发现什么特别的地方。

max_points_on_a_line

只能看自己的代码了,把代码里输出max的地方的点值都打印出来,发现求出19的地方,前两个点是一样的点,再看一下输入序列,发现有两个一样的点,再回头看公式发现问题所在。

(139,139) (139,139) (140,140) (141,141)
直接把值套进去,发现不在一条线上的点,划分到了一条线上。

对于坐标值相同的点应该特殊处理:
对于进入当前直线的第二个点(直线还没有确定),应该首先判断是否与第一个点相同,如果相同做不同的处理。



        int l=points.size();
       // cout<<l<<endl;
        if(l==1)
            return 1;

        int max=0;

        bool flag=false;  //标记点是否一样
        int repeatcount=0; //标记重复点的个数

        for(int i=0;i<l-1;i++){


            for(int j=i+1;j<l;j++){
            //  cout<<i<<"  "<<j<<" "<<l<<endl;             
                int temp=2;
                flag=false;             
                if((points[j].y==points[i].y) &&(points[j].x==points[i].x)){
                    //因为公式是基于 i,j点计算的,所以只需要计算这两个点是否重复既可以 
                    //repeatcount+=1;
                    flag=true;
                    temp=1;
                //  temp=1;
                //  max=max>temp?max:temp; 
                    repeatcount+=1;

                    temp+=repeatcount;          
                }

                //int k=((float)points[i].y-(float)points[j].y)/(points[i].x-points[j].x);
                if(!flag){
                //cout<<"Jinaliale";

                for(int t=j+1;t<l;t++){

                //  cout<<points[i].x-points[t].x<<endl;
                //  int kn=((float)points[i].y-(float)points[t].y)/(points[i].x-points[t].x);
                    float k1=((float)points[t].y-(float)points[i].y)*(points[j].x-points[i].x);
                    float k2=((float)points[j].y-(float)points[i].y)*(points[t].x-points[i].x);
                    if(k1==k2){
                        //cout<<kn<<endl;
                        temp+=1;}
                }
                //cout<<max<<endl;
                temp+=repeatcount;
                cout<<repeatcount;
                }


                max=max>temp?max:temp;
            //  cout<<"max  "<<max<<endl;
            }


            flag=false;
            repeatcount=0;
        }

        return max;
    }
};

感觉思维还是存在问题的,对于特殊情况的考虑不是特别充分。此外,当前代码循环层数太多,仍需要改进。

相关标签: C++