恩,最近还是对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
西月弦 阅读(301)
评论(0) 编辑 收藏 引用 所属分类:
解题报告