• <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>
            A Star not a Tree?
            Time Limit: 1000MS
            Memory Limit: 65536K
            Total Submissions: 2257
            Accepted: 1177

            Description

            Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allow you to connect any number of computers together in a linear arrangement. Luke is particulary proud that he solved a nasty NP-complete problem in order to minimize the total cable length.
            Unfortunately, Luke cannot use his existing cabling. The 100mbs system uses 100baseT (twisted pair) cables. Each 100baseT cable connects only two devices: either two network cards or a network card and a hub. (A hub is an electronic device that interconnects several cables.) Luke has a choice: He can buy 2N-2 network cards and connect his N computers together by inserting one or more cards into each computer and connecting them all together. Or he can buy N network cards and a hub and connect each of his N computers to the hub. The first approach would require that Luke configure his operating system to forward network traffic. However, with the installation of Winux 2007.2, Luke discovered that network forwarding no longer worked. He couldn't figure out how to re-enable forwarding, and he had never heard of Prim or Kruskal, so he settled on the second approach: N network cards and a hub.

            Luke lives in a loft and so is prepared to run the cables and place the hub anywhere. But he won't move his computers. He wants to minimize the total length of cable he must buy.

            Input

            The first line of input contains a positive integer N <= 100, the number of computers. N lines follow; each gives the (x,y) coordinates (in mm.) of a computer within the room. All coordinates are integers between 0 and 10,000.

            Output

            Output consists of one number, the total length of the cable segments, rounded to the nearest mm.

            Sample Input

            4 0 0 0 10000 10000 10000 10000 0 

            Sample Output

            28284 

            Source



            #include<cstdio>
            #include
            <cstring>
            #include
            <iostream>
            #include
            <cmath>
            using namespace std;
            const int MAXN = 150;
            const double inf = 1e250;
            int n;
            struct point{
                
            double x,y;
            }p[MAXN];
            point get_point(
            double x,double y){
                point tmp;
                tmp.x
            =x;tmp.y=y;
                
            return tmp;
            }
            double dist(point a,point b){
                
            return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
            }
            double all_dist(point a){
                
            double ans=0.0;
                
            for(int i=0;i<n;i++) ans+=dist(a,p[i]);
                
            return ans;
            }
            int main(){
                
            while(~scanf("%d",&n)){
                    
            for(int i=0;i<n;i++)
                        scanf(
            "%lf%lf",&p[i].x,&p[i].y);
                    
            double step=100.0;
                    point pp
            =p[0];
                    
            double ans=all_dist(pp);
                    
            while(step>0.2){
                        
            bool flag=true;
                        
            while(flag){
                            flag
            =false;
                            point qq
            =get_point(pp.x,pp.y+step),tt=pp;
                            
            double tmp=all_dist(qq);
                            
            if(tmp<ans) { tt=qq;ans=tmp;flag=true; }
                            qq
            =get_point(pp.x,pp.y-step);
                            tmp
            =all_dist(qq);
                            
            if(tmp<ans) { tt=qq;ans=tmp;flag=true; }
                            qq
            =get_point(pp.x+step,pp.y);
                            tmp
            =all_dist(qq);
                            
            if(tmp<ans) { tt=qq;ans=tmp;flag=true; }
                            qq
            =get_point(pp.x-step,pp.y);
                            tmp
            =all_dist(qq);
                            
            if(tmp<ans) { tt=qq;ans=tmp;flag=true; }
                            pp
            =tt;
                        }
                        step
            /=2.0;
                    }
                    printf(
            "%d\n",(int)(ans+0.5)*100/100);
                }
                
            return 0;
            }

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


            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            男女久久久国产一区二区三区| 91精品国产高清久久久久久io| 大美女久久久久久j久久| 成人亚洲欧美久久久久 | 久久精品夜夜夜夜夜久久| 久久99热只有频精品8| 99久久伊人精品综合观看| 久久久久国产精品人妻| 国产亚洲美女精品久久久久狼| 超级碰久久免费公开视频| 亚洲国产精品无码久久一区二区| 国产91久久精品一区二区| 久久久这里只有精品加勒比| 久久er热视频在这里精品| 色欲久久久天天天综合网精品| 久久精品国产99国产精品| 久久天天躁狠狠躁夜夜躁2O2O| 青青草国产97免久久费观看| 97久久香蕉国产线看观看| 久久综合久久美利坚合众国| 99久久www免费人成精品| 欧美喷潮久久久XXXXx| 久久人人爽人人爽人人片AV不| 久久99精品国产麻豆蜜芽| 精品一区二区久久久久久久网站| 麻豆av久久av盛宴av| 一97日本道伊人久久综合影院| 久久精品一区二区| 2022年国产精品久久久久| 久久99精品久久久久久动态图 | 久久99久久99精品免视看动漫| 久久国产午夜精品一区二区三区| 日韩欧美亚洲综合久久影院d3| 人妻精品久久久久中文字幕69| 久久天天躁狠狠躁夜夜不卡 | 一本综合久久国产二区| 精品久久综合1区2区3区激情| 久久精品无码一区二区三区| 久久青青草原综合伊人| 国产伊人久久| 亚洲天堂久久久|