• <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? poj2420 二分

            Posted on 2012-04-26 11:30 lenohoo 閱讀(171) 評論(0)  編輯 收藏 引用
            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;
            }

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

            Copyright © lenohoo

            69SEX久久精品国产麻豆| 国产精品久久久99| 亚洲国产精品久久久久婷婷软件 | 国产欧美一区二区久久| 久久免费精品一区二区| 精品久久久久久无码中文字幕 | 欧美精品久久久久久久自慰| 久久伊人精品青青草原高清| 久久91精品久久91综合| 色婷婷综合久久久久中文字幕| 区久久AAA片69亚洲| 久久精品视频网| 久久久无码精品亚洲日韩软件| 性色欲网站人妻丰满中文久久不卡| 国产精品久久久久久一区二区三区| 国产亚州精品女人久久久久久| 久久天天躁夜夜躁狠狠躁2022| 91麻豆精品国产91久久久久久 | 亚洲国产另类久久久精品| 久久精品视频免费| 思思久久99热只有频精品66| 99久久精品费精品国产 | 亚洲国产精品久久久久网站 | 亚洲国产精品久久久久网站 | 欧美久久久久久| 久久久久久久99精品免费观看| 国产精品久久久久a影院| 国产精品欧美久久久久天天影视| 亚洲欧美一区二区三区久久| 91性高湖久久久久| 久久久久久a亚洲欧洲aⅴ| www.久久热.com| 久久久精品人妻一区二区三区四| 久久天天躁夜夜躁狠狠| 久久久中文字幕日本| 久久精品国产清自在天天线| 久久国产午夜精品一区二区三区| 久久精品国产亚洲av麻豆色欲 | 精品久久久久久无码不卡| 青青青青久久精品国产h久久精品五福影院1421 | 成人综合久久精品色婷婷|