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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久婷婷五月综合国产尤物app| 欧美精品一区二区精品久久| 久久本道综合久久伊人| 久久综合伊人77777| 伊人久久大香线焦AV综合影院 | 午夜精品久久久久久影视riav| 2020久久精品亚洲热综合一本| 久久精品午夜一区二区福利| 国产精久久一区二区三区| 久久婷婷五月综合国产尤物app| 精品蜜臀久久久久99网站| 亚洲精品综合久久| 久久精品国产影库免费看| 少妇无套内谢久久久久| 国产999精品久久久久久| 久久久精品国产sm调教网站| 久久久久亚洲AV无码专区桃色 | 国产高潮久久免费观看| 久久综合狠狠综合久久综合88| 久久久久九国产精品| 国产精品久久久久久搜索| 无码人妻久久一区二区三区蜜桃 | 久久综合给合久久狠狠狠97色69| a级毛片无码兔费真人久久| 国产99精品久久| 狠狠综合久久综合88亚洲| 日本欧美国产精品第一页久久| 香蕉久久一区二区不卡无毒影院 | 国产精品久久久久…| 久久精品人人做人人爽电影| 久久无码精品一区二区三区| 免费观看久久精彩视频| 国产亚洲色婷婷久久99精品| 久久婷婷五月综合色奶水99啪 | 久久国产精品99精品国产| 久久久久久久久波多野高潮| 久久综合偷偷噜噜噜色| 要久久爱在线免费观看| 亚洲国产成人久久一区WWW| 热久久视久久精品18| 亚洲午夜无码久久久久|