• <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>
            樸素做法是 O(n3) 的,超時。我的做法是枚舉每個點,然后求其它點和它連線的斜率,再排序。這樣就得到經過該點的直線最多能經過幾個點。求個最大值就行了。復雜度是 O(n2logn) 的。把排序換成 hash,可以優化到 O(n2)。

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-21 18:58:04
            File Name: pku1118.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <iostream>
            #include 
            <cmath>
            using namespace std;

            #define out(x) (cout << #x << ": " << x << endl)
            typedef 
            long long int64;
            const int maxint = 0x7FFFFFFF;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template 
            <class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template 
            <class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            const int maxn = 1000;

            typedef 
            struct point_t
            {
                
            int x, y;
            }
            ;

            bool d_equal(const double &a, const double &b)
            {
                
            return abs(a - b) < 1e-9;
            }


            point_t p[maxn];
            int n;

            double slope[maxn];
            int m;

            int main()
            {
                
            while (scanf("%d"&n), n != 0)
                
            {
                    
            for (int i = 0; i < n; i++)
                        scanf(
            "%d%d"&p[i].x, &p[i].y);
                    
                    
            int ans = 0;
                    
            for (int i = 0; i < n; i++)
                    
            {
                        m 
            = 0;
                        
            for (int j = 0; j < n; j++if (i != j)
                            slope[m
            ++= double(p[j].y - p[i].y) / (p[j].x - p[i].x);
                        sort(slope, slope 
            + m);
                        
            int cnt = 1;
                        
            for (int j = 1; j < m; j++)
                        
            {
                            
            if (d_equal(slope[j], slope[j - 1]))
                                cnt
            ++;
                            
            else
                                cnt 
            = 1;
                            ans 
            >?= cnt;
                        }

                    }

                    printf(
            "%d\n", ans + 1);
                }

                
            return 0;
            }
            posted on 2007-08-21 20:37 Felicia 閱讀(470) 評論(1)  編輯 收藏 引用 所屬分類: 計算幾何
            Comments
            • # re: [計算幾何]pku1118
              古月殘輝
              Posted @ 2009-06-26 13:53
              e 這題我就是樸素的方法過的,沒有超時啊,不過運行了500ms,把你的程序提交了下,有點小錯,改了以后是300ms,沒有感覺出數量級的差別啊,不過你的Hash方法倒是蠻好的~~你都用的map實現嗎?STL會不會太慢啊?  回復  更多評論   
             
            97久久婷婷五月综合色d啪蜜芽 | 国内精品久久久久久99| 欧美精品福利视频一区二区三区久久久精品 | 亚洲午夜福利精品久久| 一本色道久久综合狠狠躁篇| 国产精品乱码久久久久久软件| 久久久久久精品免费免费自慰| 精产国品久久一二三产区区别 | 国产—久久香蕉国产线看观看| 久久久久香蕉视频| 欧美噜噜久久久XXX| 精品久久久无码中文字幕| 久久久久高潮综合影院| 国产成人精品久久| 久久精品无码一区二区无码 | 久久99精品国产99久久| 午夜精品久久影院蜜桃| 国产精品久久自在自线观看| 精品乱码久久久久久夜夜嗨| 人妻精品久久无码专区精东影业| 成人国内精品久久久久影院VR| 漂亮人妻被黑人久久精品| 无码任你躁久久久久久久| 中文字幕一区二区三区久久网站| 区久久AAA片69亚洲| 欧美亚洲另类久久综合婷婷| 亚洲午夜久久影院| 99久久精品国内| 777米奇久久最新地址| 久久久久久国产精品美女| 色狠狠久久综合网| 奇米影视7777久久精品人人爽| 久久精品成人| 久久精品国产欧美日韩| 久久国产精品无码网站| 青草影院天堂男人久久| 久久精品国产99国产精偷| 国产精品禁18久久久夂久 | 精品久久人人爽天天玩人人妻| 香港aa三级久久三级| 色综合久久久久网|