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

            The Fourth Dimension Space

            枯葉北風(fēng)寒,忽然年以殘,念往昔,語(yǔ)默心酸。二十光陰無(wú)一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢(mèng)令

            HDOJ 1007 Quoit Design 平面最近點(diǎn)對(duì)

            剛好課上學(xué)了平面最近點(diǎn)對(duì)的算法,回來實(shí)現(xiàn)以下,恩 ,分治的思想很重要。呵呵,又學(xué)會(huì)了一個(gè)算法。

            #include<iostream>
            #include
            <cstdio>
            #include
            <cmath>
            #include
            <algorithm>
            using namespace std;
            #define eps 1e-8

            const int maxn=200001;
            const double INF=999999999;

            typedef 
            struct point
            {
                
            double x,y;
                
            //int flag;
                point(){};  
            }
            point;
            point p[maxn];
            int n; 
            int cmp(double x,double y)
            {
                
            if(x==y)return 0;
                
            if(x>y)return 1;
                
            return -1
            }
                   

            bool cmp1(point a,point b)
            {
                
            if(a.x!=b.x)
                    
            return a.x<b.x;
                
            else
                    
            return a.y<b.y;
            }

            bool cmp2(int i,int j)
            {
                
            return cmp(p[i].y,p[j].y)<0;
            }

            double dist(point &a,point &b)
            {
                
            return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
            }



            int y[maxn],len;
            double cp(point p[],int l,int r)//求從l到r這些點(diǎn)的最近點(diǎn)對(duì)
            {
                
            int i,j;
                
            int mid=(l+r)>>1;
                
            double ret=INF;
                
            if(l>=r)
                    
            return ret;
                
            for(i=mid;i>=l&&!cmp(p[i].x,p[mid].x);i--);
                
            double t1=cp(p,l,i);
                
            for(i=mid;i<=r&&!cmp(p[i].x,p[mid].x);i++);
                
            double t2=cp(p,i,r);
                
            if(t1<t2)
                    ret
            =t1;
                
            else ret=t2;

                len
            =0;
                
            for(i=l;i<=r;i++)
                
            {
                    
            if(fabs(p[i].x-p[mid].x)<ret)
                        y[
            ++len]=i;
                }


                sort(y
            +1,y+len+1,cmp2);

                
            for(i=1;i<=len;i++)
                
            {
                    
            int cnt=1;
                    
            for(j=i+1;j<=len&&cnt<=7;j++)
                    
            {
                        ret
            =min(ret,dist(p[y[i]],p[y[j]])); 
                        cnt
            ++;
                    }

                }

                
            return ret;
            }


            bool check(int n)
            {
                
            int i;
                
            for(i=2;i<=n;i++)
                
            {
                    
            if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
                        
            return true;
                }

                
            return false;
            }




            int main()
            {

                
            int n;
                
            while(scanf("%d",&n)!=EOF)
                
            {    
                    
            if(n==0)
                        
            break;

                    
            int i;
                    
            for(i=1;i<=n;i++)
                        scanf(
            "%lf%lf",&p[i].x,&p[i].y);
                    sort(p
            +1,p+n+1,cmp1);
                    
            if(check(n))
                    
            {
                        printf(
            "0.00\n");
                        
            continue;
                    }

                    
            double ans=cp(p,1,n)/2;
                    printf(
            "%.2lf\n",ans);

                }

                
            return 0;    

            }












             

            posted on 2010-05-20 20:13 abilitytao 閱讀(2248) 評(píng)論(4)  編輯 收藏 引用

            評(píng)論

            # re: HDOJ 1007 Quoit Design 平面最近點(diǎn)對(duì) 2010-05-21 00:43 矩陣操作

            遍歷比較距離時(shí)你根本就不需要進(jìn)行開平方這個(gè)多余的耗時(shí)操作
            哎。。。
              回復(fù)  更多評(píng)論   

            # re: HDOJ 1007 Quoit Design 平面最近點(diǎn)對(duì)[未登錄] 2010-05-21 01:17 abilitytao

            @矩陣操作
            有道理 :-) 多謝提醒  回復(fù)  更多評(píng)論   

            # re: HDOJ 1007 Quoit Design 平面最近點(diǎn)對(duì) 2010-05-21 17:54 <A href="mailto:wolf5x1016@gmail.com"

            delaunay triangualtion  回復(fù)  更多評(píng)論   

            # re: HDOJ 1007 Quoit Design 平面最近點(diǎn)對(duì)[未登錄] 2010-05-21 19:02 abilitytao

            @&lt;A href=&quot;mailto:wolf5x1016@gmail.com&quot;
            網(wǎng)頁(yè)爬蟲?  回復(fù)  更多評(píng)論   


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


            久久国产精品77777| 四虎国产精品成人免费久久| 久久亚洲春色中文字幕久久久 | 久久亚洲AV无码精品色午夜| 亚洲精品无码久久千人斩| 97久久国产亚洲精品超碰热| 久久精品中文字幕第23页| 日韩精品久久久久久久电影| 国产91色综合久久免费| 99久久亚洲综合精品成人| 亚洲Av无码国产情品久久| 久久久久成人精品无码中文字幕 | 欧美一级久久久久久久大片| 色偷偷久久一区二区三区| 久久综合狠狠综合久久97色| 国产精品美女久久久久久2018| 亚洲国产成人久久综合碰| 久久午夜伦鲁片免费无码| 中文字幕久久亚洲一区| 国产精自产拍久久久久久蜜| 久久天天躁狠狠躁夜夜96流白浆| 久久午夜综合久久| 四虎国产精品免费久久久| 热re99久久6国产精品免费| 奇米影视7777久久精品人人爽| 嫩草影院久久99| 久久国产精品一国产精品金尊| 亚洲中文久久精品无码| 热久久最新网站获取| 午夜精品久久久久9999高清| 国产成人久久777777| 国产精品久久久久久久久鸭| 久久精品a亚洲国产v高清不卡| 亚洲AV无码久久精品狠狠爱浪潮| 一日本道伊人久久综合影| 亚洲精品tv久久久久| 欧美日韩精品久久久久| 久久久噜噜噜久久| 久久婷婷人人澡人人| 久久这里只有精品视频99| 开心久久婷婷综合中文字幕|