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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久99热精品| 91精品国产91久久久久久青草| 久久久久97国产精华液好用吗| 国产精品九九久久免费视频 | 亚洲国产小视频精品久久久三级 | 精品精品国产自在久久高清| 99久久国语露脸精品国产| 26uuu久久五月天| 国产精品99久久久精品无码| 91精品国产高清91久久久久久| 久久精品成人| 久久精品中文无码资源站 | 久久婷婷色综合一区二区| 99久久99这里只有免费的精品| 一级女性全黄久久生活片免费| 久久成人影院精品777| 亚洲欧美成人久久综合中文网| 99久久99久久久精品齐齐| 亚洲精品乱码久久久久久蜜桃| 亚洲天堂久久精品| 成人久久综合网| 色综合久久无码中文字幕| 亚洲国产成人精品久久久国产成人一区二区三区综 | 久久综合九色综合97_久久久| 久久精品国产亚洲αv忘忧草 | 日本高清无卡码一区二区久久| 1000部精品久久久久久久久| 久久亚洲精品国产亚洲老地址| 99久久精品国产一区二区蜜芽| 久久婷婷激情综合色综合俺也去| 国内精品久久久久影院亚洲| 久久精品免费网站网| 久久久久国产精品| 久久99国产亚洲高清观看首页| 久久久久99精品成人片试看| 欧洲成人午夜精品无码区久久 | 国内精品久久久久久99蜜桃| 久久成人小视频| 久久精品国产亚洲av麻豆图片| 99久久做夜夜爱天天做精品| 伊人久久大香线蕉成人|