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

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

            做法:
               歐拉定理 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 西月弦 閱讀(311) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            亚洲午夜精品久久久久久浪潮 | 亚洲AV乱码久久精品蜜桃| 91麻精品国产91久久久久| 精品无码人妻久久久久久| 亚洲AV伊人久久青青草原| 一本色道久久综合亚洲精品| 久久精品国产99久久无毒不卡| 精品久久久久久中文字幕| 国产精品免费看久久久香蕉| 亚洲国产精品无码久久青草| 久久久久亚洲AV无码专区体验| 91亚洲国产成人久久精品| 久久99热这里只频精品6| 久久99国内精品自在现线| 久久久久亚洲AV综合波多野结衣| 综合久久国产九一剧情麻豆| 国产L精品国产亚洲区久久| 日韩精品久久无码中文字幕| 久久无码一区二区三区少妇 | 99久久亚洲综合精品成人| 日本久久中文字幕| 久久国产一区二区| 色综合久久久久久久久五月| 日本精品久久久久影院日本| 亚洲嫩草影院久久精品| 久久亚洲精品无码AV红樱桃| 欧美性大战久久久久久| 国产精品免费看久久久香蕉 | 久久久久国产视频电影| 久久精品国产第一区二区三区| 亚洲国产小视频精品久久久三级 | 久久久久久亚洲AV无码专区| 久久人妻AV中文字幕| 欧美一级久久久久久久大片| 国产精品gz久久久| 色综合色天天久久婷婷基地| 久久噜噜电影你懂的| 色综合久久精品中文字幕首页| 国产精品美女久久久| 国产精品久久久福利| 国内精品久久久久久野外|