• <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>

            先求凸包,答案是凸包周長(zhǎng) + 2πl。因?yàn)楹?jiǎn)單多邊形的轉(zhuǎn)角是360度,所以加上一個(gè)圓的周長(zhǎng)。

             

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-21 15:02:36
            File Name: pku1113.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 = 1001;

            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;
            }


            point_t p[maxn];
            int n;
            point_set_c ps;
            polygon_t poly;

            int main()
            {
                
            int l;
                
            while (scanf("%d%d"&n, &l) != EOF)
                
            {
                    
            for (int i = 0; i < n; i++)
                        scanf(
            "%d%d"&p[i].x, &p[i].y);
                    ps.init(n, p);
                    poly 
            = ps.convex_hull();

                    
            double ans = 0.0;
                    
            for (int i = 0; i < poly.n; i++)
                        ans 
            += dist(poly.p[i], poly.p[(i + 1% poly.n]);
                    ans 
            += 2 * l * acos(-1.0);
                    printf(
            "%.0lf\n", ans);
                }

                
            return 0;
            }
            posted on 2007-08-21 15:43 Felicia 閱讀(495) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 計(jì)算幾何
             
            久久免费视频观看| 欧美丰满熟妇BBB久久久| 91久久九九无码成人网站| 国产精品久久网| 久久男人中文字幕资源站| 国产免费久久精品99re丫y| 久久国产乱子精品免费女| 色偷偷偷久久伊人大杳蕉| 久久国产精品99久久久久久老狼| 99久久精品国产毛片| 久久成人国产精品| 久久伊人五月天论坛| 久久99精品久久久久久久不卡| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 精品综合久久久久久98| 996久久国产精品线观看| 深夜久久AAAAA级毛片免费看| 久久久av波多野一区二区| 久久久噜噜噜久久中文字幕色伊伊| 久久精品免费一区二区| 国产精品免费久久久久影院| 狠狠色综合网站久久久久久久高清 | 久久精品国产亚洲5555| 国产成人精品白浆久久69| 最新久久免费视频| 久久久久九国产精品| 伊人久久免费视频| 精品久久久久久国产潘金莲| 久久久久精品国产亚洲AV无码| 久久影视综合亚洲| 国产精品免费久久久久影院 | 久久成人影院精品777| 久久www免费人成看片| 久久婷婷五月综合97色直播| 久久综合中文字幕| 9999国产精品欧美久久久久久| a高清免费毛片久久| 精品亚洲综合久久中文字幕| 久久99精品国产麻豆宅宅| 国产精品久久久久久久| 久久久久人妻精品一区|