• <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
            恩,最近還是對(duì)CG這方面做一下集訓(xùn)!
            題目描述:
            給出一個(gè)“一筆畫”軌跡,沒有線段重疊。求這個(gè)軌跡將平面分成了幾部分。

            tips:
               1. 其實(shí)沒有必要單獨(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 西月弦 閱讀(326) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告
            人妻中文久久久久| 午夜天堂av天堂久久久| 精品久久久久久无码专区不卡| 久久久99精品成人片中文字幕 | 精品久久久久久国产潘金莲| 一本久久综合亚洲鲁鲁五月天| AV狠狠色丁香婷婷综合久久| 丁香久久婷婷国产午夜视频| 国色天香久久久久久久小说| 久久久久亚洲AV片无码下载蜜桃| 奇米综合四色77777久久| 久久精品欧美日韩精品| 久久综合给合综合久久| 伊人久久亚洲综合影院| 久久国产精品-国产精品| 狠狠色丁香久久婷婷综合图片 | 精品国产乱码久久久久软件| 97精品久久天干天天天按摩| 波多野结衣久久| 久久久这里有精品中文字幕| 亚洲精品tv久久久久久久久| 青青青伊人色综合久久| 亚洲AV无码成人网站久久精品大| 性欧美大战久久久久久久久| 国产福利电影一区二区三区,免费久久久久久久精 | 日韩va亚洲va欧美va久久| 91精品国产高清久久久久久io | 亚洲狠狠婷婷综合久久蜜芽| 三级三级久久三级久久 | 欧美精品福利视频一区二区三区久久久精品 | 99久久精品免费观看国产| 欧美久久精品一级c片片| 久久天天躁狠狠躁夜夜2020老熟妇| 99久久国语露脸精品国产| 99久久99久久精品国产| 色综合久久天天综线观看| 亚洲成色WWW久久网站| 久久国产乱子伦精品免费强| 久久国产综合精品五月天| 久久久久亚洲AV无码观看| 久久久久人妻一区精品|