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

            學習心得(code)

            superlong@CoreCoder

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

            文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

            常用鏈接

            留言簿(4)

            我參與的團隊

            搜索

            •  

            最新隨筆

            最新評論

            • 1.?re: Poj 1279
            • 對于一個凹多邊形用叉積計算面積 后能根據結果的正負來判斷給的點集的時針方向?
            • --bsshanghai
            • 2.?re: Poj 3691
            • 你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?
            • --acmer1183
            • 3.?re: HDU2295[未登錄]
            • 這個是IDA* 也就是迭代加深@ylfdrib
            • --superlong
            • 4.?re: HDU2295
            • 評論內容較長,點擊標題查看
            • --ylfdrib
            • 5.?re: HOJ 11482
            • 呵呵..把代碼發在這里很不錯..以后我也試試...百度的編輯器太爛了....
            • --csuft1

            閱讀排行榜

            評論排行榜

            最遠點對問題

                類似于“最近點對問題”,這個問題也可以用枚舉的方法求解,時間復雜度O(n^2)。假設平面上有n個點,那么這一對最遠點必然存在于這n個點所構成的一 個凸包上,為了降低時間復雜度,可以先將這n個點按極角排序,然后利用Graham_scan法求出這個凸包,再枚舉凸包上的所有頂點(也可以用旋轉卡 殼)求出這個最遠距離,時間復雜度O(nlogn)。再最壞的情況下,如果這n個點本身就構成了一個凸包,時間復雜度為O(n^2)。該算法的平均復雜度 為O(nlogn)。
            #include <cstdio>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <cstdlib>

            const int MAXN = 100001;
            const double eps = 1e-6;
            struct point{
                
            double x,y;
            }p[MAXN],h[MAXN];

            inline 
            double distance(const point &p1,const point &p2){
                
            return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
            }
            inline 
            double multiply(const point &sp,const point &ep,const point &op){
                  
            return ((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
            }
            int cmp(const void *a,const void *b){
                point 
            *p1 = (point *)a;
                point 
            *p2 = (point *)b;
                
            double t = (p1->y-p[0].y)*(p2->x-p[0].x)-(p2->y-p[0].y)*(p1->x-p[0].x);
                
            if(t>eps) return 1;
                
            else if(fabs(t)<=eps) return 0;
                
            else return -1;
            }
            void anglesort(point p[],int n){
                
            int i,k=0;
                point temp;
                
            for(i=1;i<n;i++)
                    
            if(p[i].x<p[k].x || (p[i].x==p[k].x) && (p[i].y<p[k].y))
                        k
            =i;
                temp
            =p[0],p[0]=p[k],p[k]=temp;
                qsort(p
            +1,n-1,sizeof(point),cmp);
            }
            void Graham_scan(point p[],point ch[],int n,int &len){
                
            int i,top=2;
                anglesort(p,n);
                
            if(n<3){
                    
            for(i=0,len=n;i<n;i++) ch[i]=p[i];
                    
            return;
                }
                ch[
            0]=p[0],ch[1]=p[1],ch[2]=p[2];
                
            for(i=3;i<n;i++){
                    
            while(multiply(p[i],ch[top],ch[top-1])>=0) top--;
                    ch[
            ++top]=p[i];
                }
                len
            =top+1;
            }
            int main(){
                
            int i,j,n,len;
                
            double d,ans;
                
            while(scanf("%d",&n),n){
                    
            for(i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
                    Graham_scan(p,h,n,len);
                    
            for(ans=i=0;i<len;i++)
                        
            for(j=i+1;j<len;j++){
                            d
            =distance(h[i],h[j]);
                            
            if(d>ans) ans=d;
                        }
                    printf(
            "%.2lf\n",ans);
                }
                
            return 0;
            }


            接下來所謂旋轉卡殼法(類似求數組中最長子段的和):
            int main(){
                
            while(~scanf("%d"&n))    {
                    
            for(int i = 0; i < n; i ++)
                        p[i].read();
                    
            int top = 0;
                    tubao(p, id, n, top);
                    
            int area, area2, i, j, k, t, maxx = 0;
                    
            for(i = 0, k = 2; i < top; i ++){
                        j 
            = (i + 1% top;
                        t 
            = (k + 1% top;
                        area 
            = fabs(xmul(p[id[i]], p[id[k]], p[id[j]]));
                        area2 
            = fabs(xmul(p[id[i]], p[id[t]], p[id[j]]));
                        
            while(area < area2){    
                            area 
            = area2;
                            k 
            = (k + 1% top;
                            t 
            = (k + 1% top;
                            area2 
            = fabs(xmul(p[id[i]], p[id[t]], p[id[j]]));
                            maxx 
            = max(maxx, max( dist(p[id[i]], p[id[k]]), dist(p[id[i]], p[id[t]]) ));
                        }
                    }
                    
            if(maxx != 0)
                        printf(
            "%lf\n", maxx);
                    
            else
                        printf(
            "%lf\n", dist(p[id[0]], p[id[top-1]]));

                }

            }

            posted on 2009-08-05 11:59 superlong 閱讀(708) 評論(0)  編輯 收藏 引用
            日韩欧美亚洲国产精品字幕久久久| 亚洲精品97久久中文字幕无码 | 久久国产精品77777| 一本久久a久久精品亚洲| 久久精品无码午夜福利理论片| www.久久热.com| 一本久久综合亚洲鲁鲁五月天| 欧美黑人激情性久久| 久久精品国产亚洲AV无码娇色| 国产精品美女久久久久AV福利| 久久亚洲AV成人无码软件| 久久99国产精品一区二区| 久久精品国产99国产精品| 久久综合给合久久国产免费| 国产L精品国产亚洲区久久 | 99久久99久久精品免费看蜜桃| 91精品国产高清久久久久久国产嫩草 | 久久久久久狠狠丁香| 97视频久久久| 亚洲一区二区三区日本久久九| 久久久久亚洲av综合波多野结衣| 久久精品国产亚洲麻豆| 亚洲狠狠婷婷综合久久久久| 热久久国产欧美一区二区精品| 久久精品国产只有精品2020| 久久久久久久久久久| 午夜精品久久影院蜜桃| 99久久精品免费| 久久这里只有精品久久| 久久久噜噜噜www成人网| 久久久久av无码免费网| 久久久WWW成人| 国内精品久久久久久久coent| 久久精品www| 久久九九有精品国产23百花影院| 亚洲精品无码久久久久久| 久久受www免费人成_看片中文| 欧美粉嫩小泬久久久久久久| 久久精品国产亚洲Aⅴ香蕉| 国产精自产拍久久久久久蜜| 国产成人久久精品二区三区|