• <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 閱讀(857) 評論(0)  編輯 收藏 引用 所屬分類: Felicia 的標程計算幾何
             
            美女写真久久影院| 欧美性猛交xxxx免费看久久久| 久久综合九色综合网站| 97精品伊人久久大香线蕉| 无码人妻久久久一区二区三区| 久久人妻无码中文字幕| 久久精品国产亚洲av麻豆色欲 | 香港aa三级久久三级老师2021国产三级精品三级在| 精品久久久久久无码专区不卡| 好久久免费视频高清| 精品久久久久久国产牛牛app| 性做久久久久久久久浪潮| 久久综合亚洲欧美成人| 日韩欧美亚洲综合久久影院d3| 性欧美大战久久久久久久| 亚洲精品乱码久久久久久蜜桃不卡 | 亚洲人成网站999久久久综合 | 久久久久久久综合日本亚洲| 免费精品久久久久久中文字幕| 亚洲AV无码久久精品成人| 国产高清国内精品福利99久久| 久久精品国产色蜜蜜麻豆| 国产精品成人无码久久久久久| 免费久久人人爽人人爽av| 国产精品伊人久久伊人电影| 无码人妻少妇久久中文字幕蜜桃 | 久久精品国产亚洲7777| 伊人久久综合成人网| 久久综合亚洲鲁鲁五月天| 久久国产精品成人免费| 久久婷婷五月综合国产尤物app| 久久精品人人做人人爽电影| 99久久精品免费看国产一区二区三区| 九九99精品久久久久久| 久久影院综合精品| 亚洲精品无码专区久久同性男| 四虎国产精品免费久久久| 久久夜色精品国产噜噜亚洲AV| 日产久久强奸免费的看| 国内精品久久久久久久久电影网| 精品人妻久久久久久888|