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

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            POJ 2284 That Nice Euler Circuit---計算幾何

            Posted on 2010-09-19 01:45 Uriel 閱讀(439) 評論(0)  編輯 收藏 引用 所屬分類: POJ計算幾何
                     這幾天做計算幾何一直不順,各種WA。。這題做了一天多。。WA到哭了。。
                     這題思路很簡單,用平面圖的歐拉定理,V+F-E=2;其中V是頂點數(shù),F(xiàn)是分割出的面數(shù),E是邊數(shù)。

                     方法是:先兩重for求出所有的交點,然后判每個點在幾條線段上,每一個交點將幾條線段多分開一段。這里糾結(jié)了很久,各種WA。。無奈換思路,求出所有交點之后用set存,順便判重,然后枚舉n-1跳條線段,看每條線段上有幾個交點,但是因為線段兩端的點不會分割線段,所以要剪掉。。這里又是各種WA。。今天一晚上都杯具在這里。。然后自認為解決了這個問題之后依然WA。。無奈找到某解題報告上的數(shù)據(jù),竟然有重點,重邊。。無奈了。。各種判重,各種eps之后還是WA。。無奈找到另一份解題報告,發(fā)現(xiàn)跟我的不同之處是最后對端點的處理,判是不是一條線段的開始點,不是的話邊數(shù)就++,但是沒有判重點,重邊。。也能AC。。我改了判端點之后重點,重邊的sampl也能過。。然后總算AC了。。不過比解題報告慢很多。。set導致的。。

                    但是我的重載<跟解題報告不同,我直接!= , < 這么比的話Discuss某sample過不了,于是又加了eps才過,話說還是第一次這么寫比較函數(shù)。。= =。。弱啊。。

                    貼上丑陋的代碼一份,有錯誤歡迎大家指正

            //Problem: 2284  User: Uriel 
            //Memory: 944K  Time: 1344MS 
            //Language: C++  Result: Accepted 

            #include
            <set>
            #include
            <math.h>
            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <algorithm>
            using namespace std;
            #define eps 1e-10
            #define zero(x) (((x)>0?(x):-(x))<eps)

            struct point{
                
            double x,y;
            }
            p[100000];

            struct line{
                point a,b;
            }
            l[100000];

            bool operator<(point a,point b){
                
            if(fabs(a.x-b.x)>eps)return a.x-b.x<-eps;
                
            return a.y-b.y<-eps;
            }


            int n,E;

            double xmult(point p1,point p2,point p0){
                
            return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
            }


            int dots_inline(point p1,point p2,point p3){
                
            return zero(xmult(p1,p2,p3));
            }


            int dot_online_in(point p,point l1,point l2){
                
            return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
            }


            int same_side(point p1,point p2,point l1,point l2){
                
            return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
            }


            int intersect_in(point u1,point u2,point v1,point v2){
                
            if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
                    
            return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
                
            return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
            }


            point intersection(point u1,point u2,point v1,point v2)
            {
                point ret
            =u1;
                
            double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
                    
            /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
                ret.x
            +=(u2.x-u1.x)*t;
                ret.y
            +=(u2.y-u1.y)*t;
                
            return ret;
            }


            double len(line a){
                
            return sqrt((a.a.x-a.b.x)*(a.a.x-a.b.x)+(a.a.y-a.b.y)*(a.a.y-a.b.y));
            }


            bool ok(int x){
                
            if(len(l[x])<eps)return false;
                
            if(fabs(l[x].a.x-l[x-1].a.x)<eps && fabs(l[x].b.x-l[x-1].b.x)<eps && fabs(l[x].a.y-l[x-1].a.y)<eps && fabs(l[x].b.y-l[x-1].b.y)<eps)return false;
                
            return true;
            }


            int main(){
                
            int i,j;
                
            int cse=1;
                
            while(scanf("%d",&n),n){
                    
            for(i=0;i<n;i++)scanf("%lf %lf",&p[i].x,&p[i].y);
                    
            set<point> st;
                    E
            =0;
                    
            set<point>::iterator it;
                    
            for(i=0;i<n;i++){
                        
            for(j=0;j<n;j++){
                            
            if(i==j)continue;
                            
            if(intersect_in(p[i],p[(i+1)%n],p[j],p[(j+1)%n])){
            //                    it=st.find(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n]));
            //                    if(it==st.end())st.insert(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n]));
                                st.insert(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n]));
                            }

                        }

                    }

                    
            for(i=0;i<n;i++){
                        
            for(it=st.begin();it!=st.end();it++){
                            
            if(dot_online_in(*it,p[i],p[(i+1)%n]) && !(fabs(it->x-p[i].x)<eps && fabs(it->y-p[i].y)<eps))E++;
                        }

                    }

                    
            if(E>1)printf("Case %d: There are %d pieces.\n",cse++,E+2-st.size());
                    
            else
                        printf(
            "Case %d: There are 1 pieces.\n",cse++);
                }

                
            return 0;
            }
            无码精品久久久天天影视| 亚洲国产成人久久笫一页| 国内精品久久国产大陆| 欧美亚洲另类久久综合| 亚洲欧美成人久久综合中文网| 中文字幕精品久久| 久久综合久久综合久久| 久久91精品国产91| 91精品婷婷国产综合久久| 中文成人无码精品久久久不卡| 国产精品久久久久久影院| 亚洲精品无码久久毛片| 狠狠色丁香久久综合五月| 亚洲欧美成人久久综合中文网 | 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 东京热TOKYO综合久久精品| 国产精品嫩草影院久久| 精品国产青草久久久久福利| 久久精品国产亚洲AV久| 中文字幕成人精品久久不卡| 中文字幕人妻色偷偷久久 | 国产精品久久免费| 色欲久久久天天天综合网| 久久久久国产精品嫩草影院| 91精品国产综合久久久久久| 久久久久av无码免费网| 亚洲国产精品综合久久网络| 国产精品伊人久久伊人电影| 国产精品欧美久久久天天影视 | 99久久国产热无码精品免费| 亚洲精品午夜国产va久久| 久久精品亚洲男人的天堂| 国产精品成人无码久久久久久 | 久久中文字幕精品| 久久婷婷五月综合成人D啪| 精品久久久久久无码中文野结衣| 久久r热这里有精品视频| 久久国产精品-国产精品| 国产精品免费看久久久| 国产精品福利一区二区久久| 精品久久久久久|