青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

算法學社
記錄難忘的征途
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 西月弦 閱讀(330) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            狠狠色丁香婷婷综合久久片| 欧美综合77777色婷婷| 老司机亚洲精品| 国产精品婷婷| 亚洲精品视频一区二区三区| 国产精品久久久久久久久久免费| 一区二区三区四区国产| 欧美日韩在线免费视频| 黄色精品免费| 国产精品美女久久久久久2018| 欧美日韩久久| 亚洲欧洲日本专区| 久久免费精品视频| 久久综合给合| 亚洲午夜精品久久| 亚洲乱码国产乱码精品精| 91久久精品网| 性色av一区二区三区在线观看 | 国产一区二区| 午夜精品视频| 亚洲日本无吗高清不卡| 欧美国产高潮xxxx1819| 亚洲永久免费精品| 欧美另类在线播放| 亚洲黄色影院| 日韩视频在线一区二区| 欧美午夜久久久| 久久人人九九| 亚洲国产三级| 国产精品久久久久久久久免费| 欧美www视频| 一区二区三区久久网| 欧美激情1区2区3区| 亚洲激情成人网| 精品动漫3d一区二区三区免费| 久久国产精品一区二区三区四区| 亚洲一级黄色片| 亚洲国产精品传媒在线观看| 亚洲夜间福利| 亚洲人成网站在线观看播放| 久久国产精品第一页| 影音欧美亚洲| 午夜精品国产| 中文精品视频| 亚洲一区视频在线观看视频| 久久漫画官网| 136国产福利精品导航| 国产精品剧情在线亚洲| 欧美激情一区二区三区在线视频| 国产一区二区三区在线免费观看| 国产精品日日摸夜夜摸av| 亚洲东热激情| 欧美在线视频网站| 国产欧美在线播放| 欧美成ee人免费视频| 亚洲午夜一区二区| 亚洲成色777777女色窝| 亚洲国产成人久久| 国产亚洲va综合人人澡精品| 美女视频网站黄色亚洲| 亚洲自拍偷拍福利| 久久精品国产91精品亚洲| 久久精品国产999大香线蕉| 老色鬼精品视频在线观看播放| 中文精品视频一区二区在线观看| 欧美亚日韩国产aⅴ精品中极品| 亚洲视频综合| 亚洲综合99| 中文精品视频一区二区在线观看| 老牛影视一区二区三区| 可以免费看不卡的av网站| 欧美一区二区三区另类| 在线中文字幕一区| 午夜精品久久久久久久久久久久久 | 加勒比av一区二区| 国产精品福利av| 国产日韩亚洲欧美| 亚洲乱码日产精品bd| 亚洲看片一区| 久久高清福利视频| 亚洲精品在线看| 久久久女女女女999久久| 在线视频免费在线观看一区二区| 久久久亚洲国产美女国产盗摄| 亚洲永久精品大片| 欧美国产精品va在线观看| 久久久久久久999精品视频| 国产精品v欧美精品v日本精品动漫| 男女精品网站| 在线观看欧美日韩| 久久久青草青青国产亚洲免观| 久久爱www.| 国产女主播一区二区| 中文欧美在线视频| 中文av一区特黄| 欧美极品在线播放| 亚洲成人资源网| 亚洲国产欧美另类丝袜| 久久久之久亚州精品露出| 久久美女性网| 永久91嫩草亚洲精品人人| 久久久综合网站| 欧美承认网站| 亚洲高清毛片| 欧美精品九九| 亚洲精品在线视频| 亚洲一区二区三区在线播放| 欧美亚洲第一页| 午夜激情综合网| 久久精品国产亚洲aⅴ| 国产日产欧美精品| 久久免费黄色| 亚洲激情视频| 国产亚洲亚洲| 揄拍成人国产精品视频| 亚洲男人的天堂在线| 欧美一区二区高清在线观看| 国产精品久久看| 欧美亚洲视频在线观看| 久久综合五月天婷婷伊人| 在线电影国产精品| 欧美成熟视频| 亚洲一级一区| 久久亚洲精选| 亚洲欧洲日本mm| 国产精品毛片| 久久视频精品在线| 亚洲精品免费看| 午夜久久tv| 亚洲国产小视频| 欧美三级午夜理伦三级中文幕 | 亚洲永久免费精品| 国产婷婷一区二区| 欧美成人精品激情在线观看| 在线一区二区日韩| 中文精品99久久国产香蕉| 欧美中文字幕视频| 女女同性精品视频| 国产美女高潮久久白浆| 一区二区亚洲| 欧美成人久久| 国产精品区一区二区三| 亚洲黄页视频免费观看| 午夜国产精品视频免费体验区| 国产精品欧美久久久久无广告| 久久婷婷蜜乳一本欲蜜臀| 久久国产精品一区二区三区四区 | 日韩视频在线你懂得| 中文成人激情娱乐网| 欧美日韩综合视频| 亚洲在线日韩| 99精品视频一区| 国产精品欧美久久| 一区二区三区回区在观看免费视频| 欧美成人a∨高清免费观看| 久久久精品五月天| 国产在线精品一区二区夜色| 亚洲国产精品va在看黑人| 日韩视频在线一区| 亚洲精品偷拍| 99在线观看免费视频精品观看| 久久精品亚洲精品| 欧美三级资源在线| 欧美jizz19性欧美| 欧美激情小视频| 亚洲天堂av电影| 亚洲一区自拍| 麻豆久久婷婷| 中文在线不卡| 欧美日韩国产丝袜另类| 黄色在线一区| 久久视频国产精品免费视频在线| 亚洲精品网址在线观看| 欧美成人亚洲成人日韩成人| 小处雏高清一区二区三区| 亚洲国产精品一区二区第四页av| 久久精品免费播放| 在线日韩欧美视频| 伊人精品视频| 在线国产精品一区| 国产视频在线观看一区二区| 欧美看片网站| 国产日韩亚洲欧美综合| 一区二区精品| 亚洲激情第一页| 亚洲欧洲午夜| 亚洲另类自拍| 亚洲国产精品黑人久久久| 亚洲激情一区| 亚洲成人资源网| 亚洲久久视频| 99re6这里只有精品视频在线观看| 亚洲国产天堂久久综合网| 亚洲精品日韩在线观看| 亚洲国产一区二区三区高清| 亚洲精品三级| 亚洲最新在线| 欧美一区在线直播| 乱码第一页成人| 欧美成年人网站|