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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久青青草原精品国产软件| 国产精品久久久久aaaa| 九九久久精品国产| 亚洲精品97久久中文字幕无码| 久久久www免费人成精品| 久久久噜噜噜久久中文福利| 国产精品激情综合久久| 久久久国产精华液| 久久久久久极精品久久久| 久久久久AV综合网成人| 欧洲性大片xxxxx久久久| 成人国内精品久久久久一区| 蜜桃麻豆www久久国产精品| 久久亚洲欧美国产精品| 一级女性全黄久久生活片免费| 99久久成人国产精品免费 | 亚洲中文字幕伊人久久无码| 亚洲AV日韩精品久久久久| 久久亚洲国产成人影院网站| 久久精品黄AA片一区二区三区| 久久精品亚洲乱码伦伦中文| 国产午夜精品理论片久久影视| 久久妇女高潮几次MBA| 久久久久综合国产欧美一区二区| 91精品国产乱码久久久久久| 一本一道久久综合狠狠老| 亚洲一区精品伊人久久伊人| 久久久久久狠狠丁香| 亚洲а∨天堂久久精品| 久久强奷乱码老熟女网站| 99久久精品免费国产大片| 99久久无码一区人妻a黑| 亚洲综合熟女久久久30p| 日本WV一本一道久久香蕉| 欧洲性大片xxxxx久久久| 久久精品免费网站网| 久久精品成人一区二区三区| 国産精品久久久久久久| 久久久久亚洲av成人无码电影 | 91精品国产91久久久久久| 韩国三级大全久久网站|