对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上

max-points-on-a-line

http://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2

直接暴力破解:
第一种情况:x相同
第二种情况:y相同
第三种情况,有(a,b)(c,d)(e,f),在同一直线的判断依据是
(a-b)/(c-d) == (c-e)/(d-f)
分别计数求最大即可。

class Solution {
public:
    /**
     *
     * @param points Point类vector
     * @return int整型
     */
    int maxPoints(vector<Point>& points) {
        // write code here
        int ret = 0;
        int temp;
        map<int,int> x; // 记x相同
        map<int, int> y; // 记y相同
        Point a, b, c;
        for (auto p : points) {
            x[p.x]++;
            y[p.y]++;
        }
        float _x1, _x2, _y1, _y2; 
        for (int i = 0; i < points.size(); ++i) {
            a = points[i];
            for (int j = i+1; j < points.size(); ++j) {
                temp = 2;
                b = points[j];
                _x1 = a.x - b.x;
                _y1 = a.y - b.y;
                if (_y1 == 0) {
                    break;
                }
                for (int k = 0; k < points.size(); ++k) {
                    if (k == i || k == j)
                        continue;
                    c = points[k];
                    _x2 = b.x - c.x;
                    _y2 = b.y - c.y;
                    if (_y2 == 0) {
                        continue;
                    }
                    if (_x1 / _y1 == _x2 / _y2)
                        temp++;

                }
                if (temp > ret)
                    ret = temp;
            }
       }
        for (auto p : y) {
            if (p.second > ret)
                ret = p.second;
        }
        for(auto p:x){
            if(p.second > ret)
                ret = p.second;
        }
        return ret;
    }
};
全部评论

相关推荐

酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务