前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 149 Max Points on a Line

LeetCode 149 Max Points on a Line

作者头像
ShenduCC
发布2019-05-10 10:22:30
3210
发布2019-05-10 10:22:30
举报
文章被收录于专栏:算法修养算法修养

题目

煞笔题目,怪不得那么多人diss

两层for循环,它还疯狂卡精度,double的精度不够,必须long double

代码语言:javascript
复制
class Solution {
public:
    map<pair<long double,long double>,int> m;
    map<pair<long double,long double>,int> m2;
    map<pair<pair<long double,long double>,int>,int> m3;
    
    int maxPoints(vector<vector<int>>& points) {
        
        if(points.size()==0)
            return 0;
        int mm =1;
        
        for(int i=0;i<points.size();i++)
        {
            
            m2[make_pair(points[i][0],points[i][1])]++;
            
            mm =max(mm,m2[make_pair(points[i][0],points[i][1])]);
            
        }
        
        for(int i=0;i<points.size();i++)
        {
            for(int j=i+1;j<points.size();j++)
            {
                
                long double k;
                if(points[i][0]-points[j][0]==0)
                    k = 99999999;
                else
                    k =(long double) (points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
                long double b;
                if(points[i][0]-points[j][0]==0)
                    b = points[i][0];
                else
                    b = points[i][1] - points[i][0]*k;
                
                //k = (long double)(((long long int)(k*10000000000))/10000000000.0);
                //b = (long double)(((long long int)(b*10000000000))/10000000000.0);
            
                if(m3[make_pair(make_pair(k,b),i)]==0)
                {
                    m[make_pair(k,b)] +=1;
                    m3[make_pair(make_pair(k,b),i)]=1;
                }
                
                if(m3[make_pair(make_pair(k,b),j)]==0)
                {
                    m[make_pair(k,b)] +=1;
                    m3[make_pair(make_pair(k,b),j)]=1;
                }
                
                
            }
        }
        
        map<pair<long double,long double>,int>::iterator it;
        
        it = m.begin();
        
        while(it != m.end())
        {
            
            mm =max(mm,it->second);
            it++;
        }
        return mm;
        
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-04-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档