题目

在二维平面上，有一些点，请找出经过点数最多的那条线。

给定一个点集vectorp和点集的大小n,没有两个点的横坐标相等的情况,请返回一个vector，代表经过点数最多的那条直线的斜率和截距。

解法

自己的想法是两个点计算斜率与截距，然后另写个函数判断剩下的点到这条直线的距离。但是仔细想想复杂度还是太高了，所以采用map存储的方式:

/*

struct Point {

    int x;

    int y;

    Point() :

            x(0), y(0) {

    }

    Point(int xx, int yy) {

        x = xx;

        y = yy;

    }

};*/

class DenseLine {

public:

    vector<double> getLine(vector<Point> p, int n) {

        map<pair<double, double>, int > lines;

        for(int i = 0; i < n; i++){

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

                ++lines[calLine(p[i],p[j])];

            }

        }

        auto it = lines.begin();

        auto maxLine = it;

        int max = 0;

        while(it != lines.end()){

            if(it->second > max) maxLine = it;

            it++;

        }

        vector<double> res;

        res.push_back(maxLine->first.first);

        res.push_back(maxLine->first.second);

        return res;

    }

    pair<double, double> calLine(Point p1,Point p2){

        double k = (double)(p1.y - p2.y)/(double)(p1.x - p2.x);

        double s = (double)p1.y - (double)k*p1.x;

        return make_pair(k,s);

    }

};

pair可以将两个值视为一个单元。容器类别map和multimap就是使用pairs来管理其健值/实值(key/value)的成对元素.

巴特西

CC37:穿点最多的直线

题目

解法

最新文章

热门文章