算法学社
記錄難忘的征途
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 西月弦 阅读(287) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理