• <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 西月弦 閱讀(326) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            久久精品国产亚洲av麻豆蜜芽 | 久久综合久久性久99毛片| 久久久亚洲裙底偷窥综合| 久久久久国产精品嫩草影院 | 亚洲国产成人精品女人久久久 | 久久精品这里只有精99品| 91精品国产色综久久| 久久久青草青青国产亚洲免观| 久久天天躁狠狠躁夜夜不卡 | 亚洲中文字幕无码久久综合网| 久久久精品国产sm调教网站| 精品综合久久久久久97超人| 久久精品亚洲男人的天堂| 久久久久人妻一区精品色 | 久久久久香蕉视频| 久久偷看各类wc女厕嘘嘘| 国产精品九九久久精品女同亚洲欧美日韩综合区| 久久婷婷国产麻豆91天堂| 久久国语露脸国产精品电影| 丰满少妇高潮惨叫久久久| 亚洲午夜福利精品久久| 国产精品欧美久久久久天天影视 | www.久久99| 久久香综合精品久久伊人| 国产免费久久久久久无码| 2021久久国自产拍精品| 亚洲AV日韩精品久久久久| 无夜精品久久久久久| 老司机午夜网站国内精品久久久久久久久| 久久精品综合网| 久久精品免费网站网| 狠狠色丁香久久婷婷综| 久久国产乱子伦免费精品| 777午夜精品久久av蜜臀| 久久亚洲精品无码aⅴ大香| 亚洲日韩欧美一区久久久久我 | 久久久青草青青国产亚洲免观| 2021久久国自产拍精品| 久久综合88熟人妻| 久久久精品国产sm调教网站| 久久久久久久久久久久中文字幕 |