• <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)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            <2009年2月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久免费精品国产| 亚洲色欲久久久久综合网| 亚洲AV无码久久精品狠狠爱浪潮 | 精品久久人妻av中文字幕| 少妇精品久久久一区二区三区 | 91精品婷婷国产综合久久| 久久久久亚洲?V成人无码| 久久只有这精品99| 久久国产精品成人片免费| 久久成人国产精品一区二区| 99久久夜色精品国产网站| 亚洲欧美日韩精品久久| 欧美日韩久久中文字幕| 亚洲天堂久久精品| 久久夜色精品国产噜噜亚洲AV| 日本免费一区二区久久人人澡 | 国产一区二区精品久久凹凸| 久久香综合精品久久伊人| 色噜噜狠狠先锋影音久久| 漂亮人妻被黑人久久精品| 日日狠狠久久偷偷色综合0 | 精品久久久一二三区| 国产高潮国产高潮久久久91 | 99久久精品免费看国产一区二区三区| 久久这里只有精品首页| 欧美一级久久久久久久大片| 久久精品中文字幕久久| 久久久噜噜噜www成人网| 久久久久se色偷偷亚洲精品av| 精品国产青草久久久久福利| 久久精品嫩草影院| 国产成人精品白浆久久69| 久久久久无码精品国产不卡| 伊人久久成人成综合网222| 久久婷婷五月综合成人D啪| 久久久精品无码专区不卡| 九九热久久免费视频| 人妻少妇精品久久| 久久久久久久波多野结衣高潮| 久久精品国产亚洲AV香蕉| 久久婷婷五月综合国产尤物app |