• <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 西月弦 閱讀(318) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            久久国产成人午夜aⅴ影院 | 久久久亚洲精品蜜桃臀| 亚洲天堂久久精品| 久久久久久久久66精品片| 亚洲国产精品成人久久| 伊人久久综在合线亚洲2019| 伊人热热久久原色播放www | 久久福利片| 国产A级毛片久久久精品毛片| 久久久久免费精品国产| 久久这里只有精品首页| 国产农村妇女毛片精品久久| 亚洲级αV无码毛片久久精品| 国产视频久久| 伊人久久精品线影院| 99精品国产综合久久久久五月天| 国产精品成人99久久久久91gav| 一本色道久久综合狠狠躁| 欧美亚洲日本久久精品| 99久久99久久精品国产| 99久久国产热无码精品免费| 久久天天躁狠狠躁夜夜2020一 | 一本大道久久东京热无码AV| 久久九九亚洲精品| 99久久中文字幕| 人妻少妇久久中文字幕| 久久亚洲日韩看片无码| 欧美成人免费观看久久| 欧美亚洲国产精品久久久久| 久久99精品国产麻豆不卡| 一本久久a久久精品综合夜夜| 久久99精品久久只有精品| 久久综合精品国产二区无码| 日韩精品久久久肉伦网站 | 久久强奷乱码老熟女网站| 91精品国产高清久久久久久国产嫩草 | 99久久99这里只有免费费精品| 免费精品久久天干天干| 久久精品人人做人人爽电影| 久久久久久曰本AV免费免费| 一本色道久久综合狠狠躁|