• <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>
            posts - 74,  comments - 33,  trackbacks - 0
            There are n resting-places in the safari park. Some administrators are at the resting-places.Now we want to build a station in the park to guarantee that no animals run out of the park.Every two resting-places form a segment. If an animal runs accross a segment and thus will never be observed again, we say it is running out of the park. Lines of communication can be built between the station and a certain resting-place, but not between resting-places. Please calculate where the station should be built so that we will always know whether there are any animals running out of the park and at the same time minimize the length of the communication lines.

            Input

            The first line of input contains a positive integer, N(5<=N<=100), the number of resting-places.N lines follow. Each gives the (x,y) coordinates (in mm) of a resting-place within the park. All coordinates are integers between 0 and 10,000.

            Output

            Output consists of one number, the total distance, rounded to the nearest mm.

            This problem contains multiple test cases!

            The first line of a multiple input is an integer T, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

            The output format consists of T output blocks. There is a blank line between output blocks.

            Sample Input

            2

            8
            0 0
            1453 6432
            0 10000
            9876 1234
            10000 10000
            8754 2345
            10000 0
            2465 6843

            5
            2 2
            0 0
            2 0
            0 2
            1 1

            Sample Output

            28284

            6
            Gramham_scan代碼如下:
            #define?MAX?120
            #define?eps?1e-8
            #define?Z(x)?(((x)>0?(x):-(x))<eps)
            using?namespace?std;
            struct?P
            {
            ????
            double?x,y;?????
            }
            p1,p2;
            P?point[MAX],choose[MAX];
            double?xmult(P?p1,P?p2,P?p0)
            {
            ????
            return?(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);?
            }

            bool?cmp(P?a,P?b)
            {
            ????
            double?ret=xmult(a,b,p1);
            ????
            return?Z(ret)?(xmult(a,b,p2)>0?1:0):(ret>0?1:0);
            }

            void?Gramham(int?n,P*?p,int&?s,P*?ch)
            {
            ????
            int?i,k=0;
            ????
            for?(p1=p2=p[0],i=1;i<n;p2.x+=p[i].x,p2.y+=p[i].y,i++)
            ????????
            if?(p1.y-p[i].y>eps||(Z(p1.y-p[i].y)&&p1.x>p[i].x))
            ????????????p1
            =p[k=i];
            ????????p2.x
            /=n,p2.y/=n;
            ????????p[k]
            =p[0],p[0]=p1;
            ????????sort(p
            +1,p+n,cmp);
            ????????
            for?(ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i<n;ch[s++]=p[i++])
            ????????????
            for?(;s>2&&xmult(ch[s-1],p[i],ch[s-2])<-eps;s--);
            }

            posted on 2009-02-28 17:45 KNIGHT 閱讀(136) 評論(0)  編輯 收藏 引用
            <2009年4月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产成人无码精品久久久免费 | 久久亚洲精品国产亚洲老地址| 国产巨作麻豆欧美亚洲综合久久| 97久久精品人人澡人人爽| 欧美亚洲国产精品久久久久| 久久夜色精品国产亚洲| 国产一区二区精品久久凹凸| 91精品国产色综合久久| 久久免费视频1| 一本色道久久88加勒比—综合| 久久国产AVJUST麻豆| 91久久精品国产91性色也| 亚洲AV无码久久精品狠狠爱浪潮 | 国产99久久精品一区二区| 亚洲国产成人精品女人久久久 | 伊人久久大香线蕉AV一区二区| 亚洲精品高清久久| 久久国产精品无| 国产综合精品久久亚洲| 久久99精品久久久久久hb无码 | 国产精品久久亚洲不卡动漫| 久久天天躁狠狠躁夜夜2020一| 精品一久久香蕉国产线看播放| 精品久久亚洲中文无码| 亚洲午夜无码久久久久小说| 97久久精品午夜一区二区| 欧美牲交A欧牲交aⅴ久久| 久久精品国产第一区二区三区| 精品久久久无码21p发布| 人人狠狠综合久久亚洲| 久久九九久精品国产| 久久天天躁狠狠躁夜夜不卡 | 亚洲AV无码成人网站久久精品大| 污污内射久久一区二区欧美日韩| 久久久综合香蕉尹人综合网| 国内精品久久久久久久久电影网 | 精品久久香蕉国产线看观看亚洲| 大香网伊人久久综合网2020| 久久精品国产一区二区三区不卡 | 久久久久久综合网天天| 亚洲综合熟女久久久30p|