• <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>
            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-13 13:59:37
            File Name: convex_hull.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <iostream>
            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 = 200;

            typedef 
            struct point_t
            {
                
            int x, y;
            }
            ;

            typedef 
            struct polygon_t
            {
                
            int n;
                point_t p[maxn];
            }
            ;

            int operator <(const point_t &a, const point_t &b)
            {
                
            return a.y < b.y || a.y == b.y && a.x < b.x;
            }


            point_t 
            operator -(const point_t &a, const point_t &b)
            {
                point_t ret;
                ret.x 
            = a.x - b.x;
                ret.y 
            = a.y - b.y;
                
            return ret;
            }


            double dist(const point_t &a, const point_t &b)
            {
                
            return sqrt(double((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
            }


            int cross(const point_t &a, const point_t &b)
            {
                
            return a.x * b.y - a.y * b.x;
            }


            int turn_left(const point_t &a, const point_t &b, const point_t &c)
            {
                
            return cross(b - a, c - b) > 0;
            }


            class point_set_c
            {
            public:
                
            void init(int _n, point_t _p[]);
                polygon_t convex_hull();
            private:
                
            int n;
                point_t p[maxn];
            }
            ;

            void point_set_c::init(int _n, point_t _p[maxn])
            {
                n 
            = _n;
                
            for (int i = 0; i < n; i++)
                    p[i] 
            = _p[i];
            }


            polygon_t point_set_c::convex_hull()
            {
                
            int stack[maxn];
                
            int top = 1;
                stack[
            0= 0;

                sort(p, p 
            + n);

                
            for (int i = 1; i < n;)
                
            {
                    
            if (top == 1 || turn_left(p[stack[top - 2]], p[stack[top - 1]], p[i]))
                        stack[top
            ++= i++;
                    
            else top--;
                }

                
            int t_top = top;
                
            for (int i = n - 2; i >= 0;)
                
            {
                    
            if (top == t_top || turn_left(p[stack[top - 2]], p[stack[top - 1]], p[i]))
                        stack[top
            ++= i--;
                    
            else top--;
                }

                
                polygon_t ret;
                ret.n 
            = 0;
                
            for (int i = 0; i < top - 1; i++)
                    ret.p[ret.n
            ++= p[stack[i]];
                
            return ret;
            }
            posted on 2007-08-13 14:49 Felicia 閱讀(853) 評論(0)  編輯 收藏 引用 所屬分類: Felicia 的標程計算幾何
             
            国内精品欧美久久精品| 天天躁日日躁狠狠久久| 99久久精品国产一区二区蜜芽| 久久精品国产精品国产精品污| 久久―日本道色综合久久| 国产精品永久久久久久久久久| 国产99久久久国产精品小说| 久久久久人妻精品一区| 青青草国产成人久久91网| 欧美久久久久久精选9999| 亚洲人成网亚洲欧洲无码久久| 国产国产成人精品久久| 久久天天婷婷五月俺也去| 久久综合久久综合九色| 少妇熟女久久综合网色欲| 99久久99久久精品国产| 精品久久久中文字幕人妻 | 久久99这里只有精品国产| 国产亚洲精久久久久久无码| 久久亚洲精品国产亚洲老地址| 狠狠色丁香婷婷综合久久来| 亚洲伊人久久精品影院| 久久久久亚洲av毛片大| 人人狠狠综合久久亚洲88| 激情伊人五月天久久综合| 亚洲AV无码成人网站久久精品大| 久久亚洲国产成人影院网站| 国产成人香蕉久久久久| 久久久精品一区二区三区| 国产精品9999久久久久| 久久99国产精品尤物| 久久99国内精品自在现线| 久久精品国产亚洲av高清漫画| 国产亚洲精品久久久久秋霞| 久久国产AVJUST麻豆| 中文字幕无码久久久| 日韩精品久久久久久久电影| 日韩人妻无码一区二区三区久久99| 亚洲国产成人久久一区久久| 亚洲欧美国产日韩综合久久| 麻豆久久久9性大片|