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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久综合九色综合97_久久久| 久久精品国产2020| 久久精品国产亚洲av瑜伽| 久久久精品波多野结衣| 久久综合亚洲鲁鲁五月天| 精品久久香蕉国产线看观看亚洲| 久久激情五月丁香伊人| 亚洲国产精品18久久久久久| 99久久精品久久久久久清纯| 四虎国产精品成人免费久久| 国产精品热久久无码av| 久久久免费精品re6| 亚洲精品国精品久久99热| 国产精品久久久久久福利69堂| 亚洲欧美一级久久精品| 久久精品无码一区二区三区日韩| 日日躁夜夜躁狠狠久久AV| 亚洲国产精品嫩草影院久久| 国产成人久久精品区一区二区| 无码任你躁久久久久久| 精品无码久久久久久久久久| 久久精品人成免费| 亚洲AV无码久久精品蜜桃| 日韩美女18网站久久精品| 久久最新精品国产| 久久91精品久久91综合| 久久亚洲AV成人出白浆无码国产| 综合久久一区二区三区| 久久99精品久久久久久秒播| 欧美精品一区二区精品久久 | 精品国产乱码久久久久久人妻 | 久久人妻少妇嫩草AV无码专区| 日韩一区二区三区视频久久| 国产农村妇女毛片精品久久| 久久综合欧美成人| 草草久久久无码国产专区| 久久精品免费一区二区三区| 69久久精品无码一区二区| 久久99久久99小草精品免视看| AV色综合久久天堂AV色综合在| 国产精品久久久久久一区二区三区|