题目描述：
在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。
请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
题解：
由于本人未考虑除法的复杂性，所以用最直接的方法进行解题。首先判断点集中是否用两个点练成的线是与x轴平行的线，然后进行分类。第一类为点集中有与x轴平行的两点，然后进行依次判断其他的点是否满足与点集中任意其他一点的连线与x轴平行，进行对结果的输出；第二类即为没有与x轴平行的两点，此时采用的方法为“斜率法”，如果点集均在一条线上，那么其中相邻三点之间的斜率均相同。之前导致我一直WA的点就是该题目的接口是二维int型向量，但是我计算时虽然定义的是double型的k，却没有将进行计算的值进行转化，导致了整型相除的错误结果。
代码：
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int flag = 1;
        int zero_flag = 0;
        //找一下有没有与x轴平行的
        for(int i = 0;i < coordinates.size();i++){
            for(int j = i+1; j < coordinates.size();j++){
                if(coordinates[j][0] - coordinates[i][0] == 0){
                zero_flag = 1;
                break;
            }}
            if(zero_flag)
            break;    
        }
        //如果有跟x轴平行的，当其他的不平行是即不在一条直线
        if(zero_flag){
            int tag = 1;
            for(int i = 0;i < coordinates.size();i++){
                for(int j = i+1;j<coordinates.size();j++){
                    if(coordinates[j][0] - coordinates[i][0] !=0){
                        flag = 0;
                        tag = 0;
                        break;
                    }
                }
                if(!tag)
                break;           
            }   
        }
        else {
            double k = (double(coordinates[1][1]) - coordinates[0][1]) / (double(coordinates[1][0]) - coordinates[0][0]);
            for(int i = 0;i<coordinates.size()-1;i++){
                if(((double(coordinates[i+1][1]) - coordinates[i][1]) / (double(coordinates[i+1][0]) - coordinates[i][0])) != k){
                    flag = 0;
                    break;
                }
            }
        }
        return flag;
    }
};

这些博客作为自己的成长史，记录一下自己的进步与缺点。
很有意思的事请：
在找之前提到的数据类型错误的时候，我并没有向此方面想，是在询问朋友后再进行单步调试才发现的这个错误，然后我向他说了一句这样的话：


之后他回复我：





哈哈哈我觉得很有道理。

这道题的思路就是求斜率。斜率不同的话就不是同一直线。要注意的是求斜率时，k是double类型的所以在做除法时加上 "1.0"，我就是忘了这一点，检查了很久白白浪费了很多时间。

耗时20ms

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        if(coordinates.size() == 2)
            return true;

        int dx,dy;
        double k;

        dx = coordinates[1][0] - coordinates[0][0];
        dy = coordinates[1][1] - coordinates[0][1];

        if(dx != 0)
        {
            k = 1.0 * dy/dx;
        }

        double ki;
        int dxi,dyi;
        for(int i = 2;i < coordinates.size(); ++i )
        {
            dxi = coordinates[i][0] - coordinates[i-1][0];
            dyi = coordinates[i][1] - coordinates[i-1][1];
            if(dxi != 0)
            {
                ki = 1.0 * dyi / dxi;
                
                if(  (dx == 0) || (ki!=k) )
                    return false;
            }else{
                if(dx != 0)
                    return false;
            }
            
        }

        return true;
    }
};

 

题意理解

给定一些坐标系中的点，判断这些点是否在一条线上

问题分析

tolefttest算法

判断一个点是否在一条直线的一边，如下图



p,q是直线上的两点，s是需要判断的一点，如果s在p，q直线的左侧，面积是正；如果s在

p，q直线的右侧，面试是负；如果s在p，q直线上，面积为0.

链接

https://www.cnblogs.com/wind-chaser/p/10889537.html

其他

几何凸包计算。

下面的代码没有精炼过,就写的比较罗嗦了。



平面上任意N点,其中一条直线最多过几个点,这个题显然有O(n^2)的解法,关键的一点是一定要注意cornercase,比较多,我试了7,8次才过….首先考虑相同的点,这个要单独列出来,其次考虑不能用double表示斜率,用一个pair表示分数既可,所以要写gcd来化简,然后注意这里面有负数,所以进行构造的时候要定序,(1,-1),(-1,1)都要变成(-1,1),这样就不会少算了。最后是要注意单独考虑斜率为无穷的点,我这里单独考虑了斜率为0或者为无穷,写的比较罗嗦。最后注意线上的点的个数要加1,因为上面都是统计点的个数！

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

        int n = points.size();
        int ret = 0;
        for(int i = 0;i<= n-ret;++i){

            map<pair<int,int>,int> count;
            int maxnum = 0;
            int same = 0,vertical = 0,horizon = 0;

            for(int j = i+1;j < n;++j){

                if(points[i].x==points[j].x && points[i].y==points[j].y){
                    same+=1;
                    continue;
                }

                if(points[i].x==points[j].x){
                    vertical++;
                    continue;
                }
                else if (points[i].y == points[j].y){
                horizon++;
                continue;
                }

                auto k = line(points[i],points[j]);

                if(count.find(k)==count.end())
                    count[k] = 0;

                count[k] += 1;

                if(count[k] > maxnum)
                    maxnum = count[k];
            }
            if(maxnum+same>ret)
                ret = maxnum+same;
            if(max(vertical,horizon)+same > ret)
                ret = max(vertical,horizon)+same;
        }
        return n==0?0:ret+1;
    }


    pair<int,int> line(const Point& p1,const Point& p2){

        int dx = p1.x - p2.x;
        int dy = p1.y - p2.y;


        int g  =gcd(dx,dy);
        dx/=g;
        dy/=g;
        return pair<int,int>(min(dx,dy),max(dx,dy));



    }

    int gcd(int a,int b){

        if(a<b)
        return gcd(b,a);

        while(a%b){
            int t = a%b;
            a = b;
            b = t;

        }
        return b;

    }

};