• <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 的標程計算幾何
             
            久久国产高潮流白浆免费观看| 精品人妻久久久久久888| 亚洲国产精品久久久久婷婷软件 | 亚洲级αV无码毛片久久精品| 午夜精品久久久久久毛片| 久久99国产综合精品女同| 99久久99久久精品国产片果冻| 色妞色综合久久夜夜| 久久精品成人免费网站| 久久精品免费网站网| 久久天天躁狠狠躁夜夜网站| 久久精品亚洲乱码伦伦中文| 久久久久久夜精品精品免费啦 | 久久成人永久免费播放| 少妇人妻88久久中文字幕| 国产综合精品久久亚洲| 久久99精品久久久久子伦| 一级女性全黄久久生活片免费 | 男女久久久国产一区二区三区 | 91久久精品无码一区二区毛片| 精品国产乱码久久久久软件| 亚洲国产成人久久精品动漫| 一本色道久久综合狠狠躁| 国产综合免费精品久久久| 国产一久久香蕉国产线看观看| 久久人妻AV中文字幕| 无码任你躁久久久久久久| 国产成人99久久亚洲综合精品| 色婷婷综合久久久久中文一区二区 | 天天综合久久一二三区| 国产亚州精品女人久久久久久 | 久久国产亚洲高清观看| 国产成人精品三上悠亚久久| 中文字幕久久亚洲一区| 亚洲&#228;v永久无码精品天堂久久| 国内精品伊人久久久久AV影院| 一本色综合网久久| 久久久精品人妻一区二区三区蜜桃| 伊人久久综合成人网| 国内精品久久久久久99蜜桃| 久久婷婷五月综合色高清|