• <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 閱讀(130) 評論(0)  編輯 收藏 引用 所屬分類: LeetCode
            這題POJ上有原題,平面上一堆點,求最多共線點數,方法不難,1~n枚舉所有點,求它和其他點分別構成直線的斜率,然后sort,然后算有幾個相同斜率的,求個max
            這題的trick在于有重復點,為了處理這個搞了半天【我太挫...然后用的是很Naive的辦法,重復點單獨計數單獨算,另外斜率不存在的時候設為一個很大的數(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 };
            少妇久久久久久被弄高潮| 久久se精品一区二区| 91久久精品视频| 久久天天日天天操综合伊人av| 久久久久久久久久久免费精品| 欧美性猛交xxxx免费看久久久| 伊人久久大香线蕉亚洲五月天| 国产99久久精品一区二区| 亚洲人成无码久久电影网站| 久久综合精品国产二区无码| 激情五月综合综合久久69| 久久综合精品国产二区无码| 久久性生大片免费观看性| 精品无码久久久久久午夜| 狠狠色伊人久久精品综合网| 久久久精品人妻一区二区三区四| 久久久久99精品成人片| 91精品国产91久久综合| 亚洲国产成人精品91久久久 | 91精品国产91久久久久久青草| 精品久久久无码中文字幕| 久久久久人妻精品一区| 亚洲精品99久久久久中文字幕| 热99re久久国超精品首页| 久久久久久亚洲精品成人 | 久久精品二区| www.久久热.com| 少妇高潮惨叫久久久久久| 精品久久久久久无码不卡| 久久久久婷婷| 久久久WWW成人| 久久精品二区| 久久精品国产一区二区| 久久国产精品无码网站| 久久国产成人亚洲精品影院| 国产精品无码久久综合网| 97久久精品人人澡人人爽| 26uuu久久五月天| 99久久无码一区人妻| 久久99精品国产麻豆蜜芽| 精品久久久久中文字|