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

算法學社
記錄難忘的征途
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久久精品日日躁夜夜躁国产| 9国产精品视频| 久久精品国产清自在天天线| 亚洲国产91| 一本久道久久综合中文字幕| 欧美亚洲一区二区在线观看| 欧美成人精品一区| 国产亚洲精品aa| 中文精品99久久国产香蕉| 久久精品国产亚洲一区二区| 99精品视频免费在线观看| 亚洲日本中文字幕区| 久久国产视频网站| 国产精品成人观看视频免费| 红桃视频国产一区| 亚洲欧美中文在线视频| 亚洲国产欧美日韩| 西西人体一区二区| 亚洲黄色成人网| 午夜精品福利一区二区蜜股av| 欧美在线视频一区二区| 国产精品人成在线观看免费 | 欧美日韩一区在线视频| 黑人极品videos精品欧美裸| 国产精品99久久99久久久二8| 久久精品九九| 99国产精品视频免费观看一公开| 午夜亚洲视频| 伊人蜜桃色噜噜激情综合| 久久裸体艺术| 欧美一二三区在线观看| 国产欧亚日韩视频| 久久久精品一区二区三区| 久久精品99久久香蕉国产色戒| 国产区欧美区日韩区| 久久国产免费| 欧美99久久| 久久岛国电影| 男人插女人欧美| 翔田千里一区二区| 久久久久久综合网天天| 正在播放亚洲| 久久久久91| 午夜视黄欧洲亚洲| 你懂的亚洲视频| 午夜久久资源| 欧美国产一区视频在线观看| 欧美第一黄色网| 久久精品国产亚洲一区二区三区| 欧美韩日精品| 欧美成人在线影院| 国产日产高清欧美一区二区三区| 亚洲区中文字幕| 永久91嫩草亚洲精品人人| 欧美一区二区三区免费在线看| 99精品视频免费全部在线| 美女诱惑黄网站一区| 美女免费视频一区| 亚洲国内自拍| 裸体歌舞表演一区二区| 欧美成在线视频| 亚洲福利视频专区| 免费不卡在线观看av| 母乳一区在线观看| 亚洲激情一区| 欧美午夜视频一区二区| 欧美一区日韩一区| 嫩草国产精品入口| 亚洲六月丁香色婷婷综合久久| 久久久福利视频| 一本色道久久99精品综合| 亚洲欧美网站| 91久久精品www人人做人人爽| 欧美激情日韩| 欧美一区二区视频97| 老司机精品久久| 亚洲性视频网站| 国产一区二区三区电影在线观看| 另类专区欧美制服同性| 亚洲一级特黄| 亚洲黄色精品| 亚洲国产一区视频| 欧美激情一区二区三区在线视频观看| 欧美在线观看视频在线| 狠狠色丁香婷婷综合影院 | 亚洲国产成人久久综合| 欧美激情导航| 亚洲欧美日韩在线一区| 亚洲欧洲精品一区二区三区| 欧美国产日韩一区二区三区| 亚洲一级二级在线| 一区二区三区欧美视频| 日韩视频免费| 日韩视频免费在线观看| 国产性猛交xxxx免费看久久| 欧美三级在线视频| 欧美日韩国产一区二区| 欧美精品免费视频| 欧美日本国产一区| 国产一区二区视频在线观看| 国产精品都在这里| 欧美精品久久天天躁| 一区二区高清在线| 一区二区欧美精品| 欧美激情2020午夜免费观看| 欧美日本三区| 一本色道婷婷久久欧美| 亚洲视频在线播放| 伊人久久亚洲美女图片| 亚洲国产精彩中文乱码av在线播放| 一区二区三区在线免费观看| 亚洲国产高清一区二区三区| 免费视频久久| 亚洲视频在线一区| 一区二区三区av| 国产精品乱码妇女bbbb| 亚洲国产日韩欧美在线99| 国产日韩欧美一区二区| 中文在线资源观看视频网站免费不卡| 亚洲欧美日韩久久精品 | 日韩一级精品| 亚洲国产女人aaa毛片在线| 国产一区二区三区日韩| 亚洲一区二区在线看| 91久久久久久| 亚洲桃花岛网站| 亚洲人成在线影院| 一区二区免费在线观看| 香蕉亚洲视频| 久久综合99re88久久爱| 欧美在线影院| 一区二区三区国产在线| 91久久在线观看| 久久免费视频在线| 国产伦精品一区二区三区照片91| 亚洲欧美日韩综合aⅴ视频| 亚洲激情图片小说视频| 欧美日韩亚洲高清一区二区| 欧美成人嫩草网站| 欧美一区不卡| 亚洲男女毛片无遮挡| 亚洲欧洲精品一区二区三区不卡 | 国产精品99久久久久久www| 欧美黄色片免费观看| 亚洲综合大片69999| 亚洲免费中文| 国产视频在线观看一区二区| 亚洲精品国产精品久久清纯直播| 你懂的视频欧美| 亚洲欧美日韩精品久久久| 午夜精品婷婷| 欧美影院午夜播放| 欧美先锋影音| 日韩一级片网址| 午夜影视日本亚洲欧洲精品| 久久一区中文字幕| 亚洲黄色小视频| 亚洲女性喷水在线观看一区| 欧美精品123区| 免费久久精品视频| 免费看的黄色欧美网站| 久久福利视频导航| 日韩亚洲欧美一区二区三区| 国产视频观看一区| 国产三级欧美三级| 亚洲另类自拍| 亚洲一区二区黄| 亚洲一区二区三区成人在线视频精品 | 国产精品久久久免费| 性一交一乱一区二区洋洋av| 久久久久久高潮国产精品视| 国产小视频国产精品| 亚洲成色最大综合在线| 欧美一级在线亚洲天堂| 欧美日韩一区高清| 91久久在线观看| 欧美凹凸一区二区三区视频| 免费成人小视频| 国产精品一卡二| 欧美在线啊v| 看欧美日韩国产| 亚洲视屏在线播放| 免费在线视频一区| 亚洲第一色中文字幕| 欧美一区亚洲二区| 日韩视频免费在线| 欧美黄色日本| 日韩视频一区二区在线观看 | 在线亚洲电影| 欧美一区二区成人6969| 久久精品国产99国产精品|