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

算法學社
記錄難忘的征途
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>
            久久久久久亚洲综合影院红桃 | 欧美日韩精品一区二区| 欧美专区亚洲专区| 久久精品国产91精品亚洲| 羞羞色国产精品| 久久精品91| 免费看成人av| 欧美久久婷婷综合色| 国产精品毛片a∨一区二区三区|国 | 亚洲高清精品中出| 免费在线亚洲| 亚洲激情视频在线| 亚洲一区在线免费| 欧美亚洲视频在线观看| 久久综合久久88| 欧美精品粉嫩高潮一区二区 | 欧美一区二区三区日韩视频| 久久精品国产一区二区三| 久久久国产一区二区| 欧美成人精品激情在线观看| 国产精品久久久久国产a级| 国产性天天综合网| 亚洲国产一区二区视频| 亚洲一区国产视频| 蜜臀av性久久久久蜜臀aⅴ四虎| 亚洲精品资源| 久久久www成人免费毛片麻豆| 欧美日韩免费一区二区三区视频 | 黑人中文字幕一区二区三区 | 亚洲欧美久久| 欧美国产高清| 欧美中文字幕在线播放| 欧美日韩国产综合视频在线观看中文| 国产亚洲福利社区一区| 99国产精品久久| 久久久久久亚洲精品不卡4k岛国| 亚洲精品久久久久中文字幕欢迎你| 欧美亚洲日本网站| 欧美日韩综合精品| 91久久久久久| 久久亚洲风情| 香蕉乱码成人久久天堂爱免费 | 久久精品女人| 一区二区三区视频观看| 另类天堂视频在线观看| 国产日韩欧美另类| 亚洲一区二区成人| 亚洲国产精品va在线看黑人动漫| 久久精品视频在线观看| 国产日韩亚洲| 欧美淫片网站| 亚洲自拍16p| 国产精品卡一卡二| 亚洲女爱视频在线| 日韩一级网站| 欧美日韩免费观看一区三区| 亚洲理论在线观看| 亚洲大片免费看| 蜜桃av久久久亚洲精品| 1000部国产精品成人观看 | 一区二区日韩伦理片| 欧美承认网站| 亚洲国产欧美一区| 欧美国产日韩一区二区| 久久久青草婷婷精品综合日韩| 国产亚洲精品aa| 久久久免费av| 久久久精品国产99久久精品芒果| 国内激情久久| 免费视频一区| 免费在线成人av| 日韩网站在线观看| 99视频一区| 国产精品久久久对白| 久久av资源网站| 欧美一级久久| 尤妮丝一区二区裸体视频| 久久综合中文| 欧美激情影音先锋| 亚洲一区二区精品| 亚洲嫩草精品久久| 尤物视频一区二区| 欧美激情网站在线观看| 欧美日韩国产一区精品一区| 午夜精品www| 欧美一区二区三区日韩| 亚洲国产精品久久久久婷婷884| 亚洲电影中文字幕| 欧美系列精品| 久久久久久久久久久久久9999| 久久久.com| 亚洲精品无人区| 亚洲天堂网站在线观看视频| 国产一区二区三区日韩| 欧美国产日韩免费| 欧美午夜精品久久久久久超碰| 亚洲欧美日韩精品一区二区| 欧美一区二区三区男人的天堂 | 欧美日韩精品一本二本三本| 欧美一区二区视频在线| 久久综合九色综合欧美狠狠| 在线视频精品一区| 久久婷婷国产综合国色天香| 欧美高清一区二区| 亚洲欧美经典视频| 另类亚洲自拍| 久久精品日韩| 欧美日韩国产精品一卡| 久久精品伊人| 欧美日韩免费观看一区| 免费黄网站欧美| 欧美午夜无遮挡| 欧美成人在线网站| 国产精品综合网站| 91久久精品国产91性色| 韩国亚洲精品| 亚洲欧美日韩天堂一区二区| 亚洲久久一区| 久久夜色精品国产噜噜av| 亚洲欧美影音先锋| 欧美精品一级| 欧美激情久久久久| 国产一区二区三区四区| 一区二区三区成人| 日韩视频在线观看一区二区| 久久九九全国免费精品观看| 欧美怡红院视频一区二区三区| 欧美日韩高清一区| 久久久精品国产免费观看同学| 国产精品99一区| 亚洲精品国精品久久99热一| 亚洲国产日韩美| 久久久久久久综合色一本| 久久av资源网站| 国产乱码精品1区2区3区| 野花国产精品入口| 亚洲精品视频在线| 欧美国产日韩一区二区| 欧美黄在线观看| 亚洲国产精品成人一区二区| 欧美影院视频| 久久久久久久综合| 国产视频一区在线观看一区免费| 亚洲视频1区| 午夜国产不卡在线观看视频| 国产精品久久久久久久久久尿| 一区二区三区四区五区在线| 亚洲视频一区| 欧美新色视频| 亚洲在线黄色| 久久久久99| 亚洲第一黄色| 欧美韩日亚洲| 9色porny自拍视频一区二区| 亚洲一区二区在线视频| 久久只精品国产| 亚洲高清不卡一区| 日韩一级大片在线| 欧美日韩综合视频| 亚洲影视在线播放| 久久久久久久久蜜桃| 悠悠资源网久久精品| 欧美高清影院| 亚洲小说春色综合另类电影| 久久久精品视频成人| 亚洲电影有码| 欧美日韩在线免费视频| 亚洲女同精品视频| 免费欧美电影| 亚洲午夜免费福利视频| 国产视频在线观看一区二区| 亚洲高清在线| 亚洲一区不卡| 亚洲成人资源| 欧美午夜视频在线观看| 久久久精品一品道一区| 91久久久久久国产精品| 亚洲欧美一区二区在线观看| 尤物精品国产第一福利三区| 欧美体内she精视频在线观看| 欧美伊久线香蕉线新在线| 亚洲国产成人tv| 久久激情综合网| 一本色道久久综合狠狠躁篇怎么玩| 国产精品日日摸夜夜摸av| 浪潮色综合久久天堂| 99综合视频| 欧美国产精品久久| 性18欧美另类| 99成人精品| 91久久精品美女高潮| 国产日韩欧美一区在线 | 亚洲欧美日韩国产中文| 亚洲盗摄视频| 国产美女诱惑一区二区| 欧美人妖另类| 可以看av的网站久久看| 欧美一区观看| 亚洲一区二区三区高清不卡| 亚洲国产日韩精品|