穿点最多的直线LeetCode中等题

穿点最多的直线LeetCode中等题

已知一个点集vectorp和点集的大小n,点都在一个二维平面上且横坐标各不相同,找到一条穿过点数最多的直线，返回值为vector，代表所求直线的斜率和截距。

方法一：线性回归方程

class DenseLine {
public:
    vector getLine(vector p, int n) {
        // write code here
        double xave = 0, yave = 0, up = 0, down = 0;
        for(int i = 0; i < n; i++){
            xave += p[i].x;
            yave += p[i].y;
        }
        xave /= n;
        yave /= n;
        for(int i = 0; i < n; i++){
            up += (p[i].x - xave) * (p[i].y - yave);
            down += (p[i].x - xave) * (p[i].x - xave);
        }
        double k = up / down;
        double b = yave - k*xave;
        return vector ({k, b});
    }
};

方法二：暴力解法

class DenseLine {
public:
    vector getLine(vector p, int n) {
        // write code here
        map, int> mp;
        for(int i=0; isecond > index->second) index = it;
        }
        return vector ({index->first.first, index->first.second});
    }
    pair calLine(Point p1, Point p2){
        double k = (double)(p1.y - p2.y)/(p1.x - p2.x);
        double b = (double)p1.y - k*p1.x;
        return make_pair(k, b);
    }
};