• <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>
            算法學(xué)社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            恩,最近還是對CG這方面做一下集訓(xùn)!
            題目描述:
            給出一個“一筆畫”軌跡,沒有線段重疊。求這個軌跡將平面分成了幾部分。

            tips:
               1. 其實沒有必要單獨(dú)寫線段相交的部分的,直接寫成直線相交就可以了。然后判斷交點(diǎn)是否在線段上!
               2. 直線相交,用參數(shù)方程表示直線。原理貌似還是定比分點(diǎn)。
               3. complex 沒有重載 “<” 運(yùn)算符

            做法:
               歐拉定理 f + c = e + 2

            代碼:
                
            1 #include<iostream>
             2 #include<cstdio>
             3 #include<complex>
             4 #include<cmath>
             5 #include<algorithm>
             6 using namespace std;
             7 #define X(a) real(a)
             8 #define Y(a) imag(a)
             9 #define eps 1e-10
            10 const int N = 310;
            11 typedef complex<double> pnt;
            12 pnt p[N], v[N*N];
            13 int sign(double x){if(abs(x) < eps) return 0; else if(x > 0) return 1; else return -1;};
            14 static double dot(pnt x,pnt y){return X(conj(x)*y);}
            15 static double cross(pnt x, pnt y){return Y(conj(x)*y);}
            16 bool cmp (const pnt &a,const pnt &b) {
            17     return sign(X(a) - X(b)) == 0 ? Y(a) < Y(b) : X(a) < X(b);
            18 }
            19 bool is_seg_insect(pnt a,pnt b,pnt x,pnt y){
            20     return sign(cross(y-x,a-x)) * sign(cross(y-x,b-x)) < 0 && sign(cross(b-a,x-a)) * sign(cross(b-a,y-a)) < 0;
            21 };
            22 pnt lin_insect(pnt p,pnt v,pnt q,pnt w){
            23     pnt u = p - q;
            24     double t = cross(w,u) / cross(v,w);
            25     return p + t * v;
            26 };
            27 bool is_onseg_prop(pnt p,pnt a1,pnt a2){
            28 //    cout<<p <<" "<<a1<<" "<<a2<<endl;
            29     return sign(cross(a1-p,a2-p)) == 0 && sign(dot(a1-p,a2-p)) < 0;
            30 };
            31 int main(){
            32     int n,cas = 1;
            33     while(cin >> n && n){
            34         int e = n - 1, c = n;
            35         for(int i = 0; i < n; i++){
            36             double x,y;
            37             scanf("%lf%lf",&x,&y);
            38             p[i] = pnt(x,y);
            39             v[i] = p[i];
            40         }
            41         for(int i = 0; i < n-1; i++)
            42             for(int j = i+1; j < n-1; j++) if(is_seg_insect(p[i],p[i+1],p[j],p[j+1])){
            43                 v[c++] = lin_insect(p[i],p[i] - p[i+1],p[j],p[j] - p[j+1]);
            44             }
            45         sort(v,v+c,cmp);
            46         c = unique(v , v + c) - v;
            47         for(int i = 0; i < n -1; i++)
            48             for(int j = 0; j < c; j++)
            49                 if(is_onseg_prop(v[j],p[i],p[i+1])) e ++;
            50         int ans = e + 2 - c;
            51         printf("Case %d: There are %d pieces.\n",cas ++, ans);
            52     }
            53 }
            posted on 2013-05-06 14:07 西月弦 閱讀(318) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            亚洲欧美久久久久9999| 久久棈精品久久久久久噜噜| 欧美大战日韩91综合一区婷婷久久青草 | 久久人人爽人人爽人人爽 | 久久无码专区国产精品发布| 99久久免费只有精品国产| 久久亚洲精品中文字幕| 天堂久久天堂AV色综合| 久久久精品2019免费观看| 91麻豆国产精品91久久久| 久久伊人精品一区二区三区| 久久久久亚洲精品日久生情| 亚洲愉拍99热成人精品热久久| 欧美日韩精品久久久免费观看| 亚洲伊人久久综合影院| 久久亚洲精品国产亚洲老地址 | 99久久精品午夜一区二区| 久久精品无码专区免费青青 | 久久婷婷五月综合色奶水99啪 | 2022年国产精品久久久久| 久久久国产精品网站| 91精品国产91久久久久久青草| 久久人人爽人人爽人人片AV东京热| 国产亚洲美女精品久久久| 欧美日韩精品久久免费| 久久香综合精品久久伊人| 久久99热只有频精品8| 久久被窝电影亚洲爽爽爽| 国产巨作麻豆欧美亚洲综合久久| 久久久久99精品成人片三人毛片| 青青草原综合久久大伊人| 国产精品美女久久久久久2018| 国产精品免费看久久久香蕉| 精品久久久久久无码不卡| 成人国内精品久久久久一区| 久久久久亚洲?V成人无码| 亚洲中文字幕久久精品无码喷水 | 国产精品久久久久无码av| 欧美亚洲另类久久综合婷婷| 69国产成人综合久久精品| 无码任你躁久久久久久老妇|