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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久国产一区二区| 93精91精品国产综合久久香蕉| 亚洲精品乱码久久久久久| 久久亚洲色一区二区三区| 亚洲AV无码1区2区久久 | 狠狠色丁香久久婷婷综合蜜芽五月 | 久久久久夜夜夜精品国产| 久久AV无码精品人妻糸列| 欧美伊人久久大香线蕉综合| 久久午夜羞羞影院免费观看| 久久91亚洲人成电影网站| 久久影院亚洲一区| www.久久99| 少妇熟女久久综合网色欲| 精品免费tv久久久久久久| 亚洲欧美久久久久9999| 女人香蕉久久**毛片精品| 久久午夜夜伦鲁鲁片免费无码影视| 国产麻豆精品久久一二三| 伊人色综合九久久天天蜜桃 | 久久99精品国产麻豆不卡| 无码精品久久久久久人妻中字| 久久精品无码一区二区三区| 精品久久人人爽天天玩人人妻| 99久久夜色精品国产网站| 99久久国产综合精品麻豆| 性色欲网站人妻丰满中文久久不卡| 久久精品国产99久久丝袜| 国产亚洲色婷婷久久99精品| 777午夜精品久久av蜜臀| 午夜精品久久久久久| 久久91精品综合国产首页| 国产精品久久永久免费| 国产成人久久精品一区二区三区| 狠狠综合久久AV一区二区三区| 欧美日韩中文字幕久久久不卡| 亚洲午夜久久影院| 爱做久久久久久| 国内精品久久久久久中文字幕| 久久精品国产一区| 久久精品?ⅴ无码中文字幕|