恩，最近還是對(duì)CG這方面做一下集訓(xùn)！
題目描述：
給出一個(gè)“一筆畫”軌跡，沒有線段重疊。求這個(gè)軌跡將平面分成了幾部分。
tips:
1. 其實(shí)沒有必要單獨(dú)寫線段相交的部分的，直接寫成直線相交就可以了。然后判斷交點(diǎn)是否在線段上！
2. 直線相交，用參數(shù)方程表示直線。原理貌似還是定比分點(diǎn)。
3. complex 沒有重載 “<” 運(yùn)算符
做法：
歐拉定理 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)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告