• <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年2月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            午夜精品久久久久久影视riav| 四虎影视久久久免费观看| 久久精品国产亚洲7777| 亚洲精品蜜桃久久久久久| 久久久人妻精品无码一区| 69SEX久久精品国产麻豆| 久久久无码一区二区三区| 久久久无码精品亚洲日韩软件| 久久免费精品一区二区| 国产精品久久亚洲不卡动漫| 久久久精品国产sm调教网站| 婷婷久久久亚洲欧洲日产国码AV | 久久精品青青草原伊人| 久久久久亚洲AV无码去区首| 国产福利电影一区二区三区久久久久成人精品综合 | 亚洲国产视频久久| 一本色道久久88综合日韩精品 | 亚洲精品乱码久久久久久久久久久久| 久久九九青青国产精品| 99精品久久久久久久婷婷| 久久丝袜精品中文字幕| 一级做a爰片久久毛片人呢| 久久99久久99精品免视看动漫| 久久国产欧美日韩精品免费| 国产午夜精品理论片久久| 青青热久久综合网伊人| 国产精品久久影院| 蜜桃麻豆www久久| 香蕉久久夜色精品国产小说| 色综合久久中文综合网| segui久久国产精品| 久久久久久国产a免费观看黄色大片 | 久久精品国产福利国产秒| 粉嫩小泬无遮挡久久久久久| 91精品国产9l久久久久| 99久久精品无码一区二区毛片| 91精品国产乱码久久久久久| 久久99国产精品久久久| 9999国产精品欧美久久久久久| 老司机午夜网站国内精品久久久久久久久 | 欧美日韩成人精品久久久免费看|