• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            [LeetCode]Max Points on a Line-2014.01.05

            Posted on 2014-01-11 01:54 Uriel 閱讀(129) 評論(0)  編輯 收藏 引用 所屬分類: LeetCode
            這題POJ上有原題,平面上一堆點,求最多共線點數(shù),方法不難,1~n枚舉所有點,求它和其他點分別構(gòu)成直線的斜率,然后sort,然后算有幾個相同斜率的,求個max
            這題的trick在于有重復(fù)點,為了處理這個搞了半天【我太挫...然后用的是很Naive的辦法,重復(fù)點單獨計數(shù)單獨算,另外斜率不存在的時候設(shè)為一個很大的數(shù)(1e10)

             1 /**
             2  * Definition for a point.
             3  * struct Point {
             4  *     int x;
             5  *     int y;
             6  *     Point() : x(0), y(0) {}
             7  *     Point(int a, int b) : x(a), y(b) {}
             8  * };
             9  */
            10 class Solution {
            11 public:
            12     struct pt{
            13         double k;
            14         int fg;
            15         bool operator<(const pt &m)const {
            16             return k < m.k;
            17         }
            18     }pp[1010];
            19     int maxPoints(vector<Point> &points) {
            20         int max = 0, pre_max = 0;
            21         int cnt = points.size();
            22         for(int i = 0; i < cnt; ++i) {
            23             int nt = 0, nnt = 0;
            24             for(int j = i; j < cnt; ++j) {
            25                 if((points[j].x - points[i].x) < -1e-6 || (points[j].x - points[i].x) > 1e-6) {
            26                     pp[j].k = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
            27                     pp[j].fg = 0;
            28                 }
            29                 else if((points[j].x - points[i].x) > -1e-6 && (points[j].x - points[i].x) < 1e-6 && (points[j].y - points[i].y) > -1e-6 && (points[j].y - points[i].y) < 1e-6) {
            30                     pp[j].fg = 1;
            31                     nnt++;
            32                 }
            33                 else {
            34                     pp[j].k = 1e10;
            35                     pp[j].fg = 0;
            36                 }
            37             }
            38             sort(pp + i + 1, pp + cnt);
            39             for(int j = i + 2; j < cnt; ++j) {
            40                 if(pp[j].fg) continue;
            41                 else {
            42                     if(!nt) nt = 1;
            43                     if(pp[j - 1].k == pp[j].k) nt++;
            44                     else {
            45                         if(nt + nnt> max) max = nt + nnt;
            46                         nt = 1;
            47                     }
            48                 }
            49             }
            50             if(nt + nnt> max) max = nt + nnt;
            51             if(nnt < cnt - i && nnt + 1 > max) max = nnt + 1;
            52         }
            53         if(cnt > 2)
            54             return max;
            55         else
            56             return cnt;
            57     }
            58 };
            伊人久久一区二区三区无码| 亚洲国产精品久久久久久| 青草影院天堂男人久久| 少妇久久久久久久久久| 欧美日韩精品久久免费| 久久无码AV中文出轨人妻| 久久精品综合网| 亚洲国产另类久久久精品小说| 狠狠色丁香久久婷婷综合图片| 一本色综合久久| 午夜不卡久久精品无码免费| 亚洲香蕉网久久综合影视| 国内精品伊人久久久久av一坑| 九九久久自然熟的香蕉图片| 久久精品国产亚洲AV麻豆网站 | www.久久热.com| 久久国产精品久久| 狠狠色伊人久久精品综合网 | 久久精品国产亚洲AV无码娇色 | 亚洲伊人久久成综合人影院| 91麻豆国产精品91久久久| 亚洲AV无码1区2区久久 | 99久久www免费人成精品| 久久播电影网| 亚洲AV无码成人网站久久精品大| 亚洲午夜久久久久久噜噜噜| 91精品国产高清91久久久久久| 精品久久久无码中文字幕天天| 中文字幕亚洲综合久久菠萝蜜| 久久久免费精品re6| 狠狠久久综合伊人不卡| 亚洲精品无码久久一线| 老司机国内精品久久久久| 一本久久a久久精品综合香蕉| 久久ZYZ资源站无码中文动漫| 久久se这里只有精品| 久久精品国产清高在天天线| 久久男人中文字幕资源站| 97久久超碰国产精品旧版| 国产精品久久久久久久久软件| 91精品国产综合久久四虎久久无码一级|