本題用到平面圖的歐拉公式：設平面圖的頂點數、邊數和面數分別為V,E,F，則V+F-E=2. 1.在求頂點數V的時候，很容易想到的想法是判斷線段兩兩相交，如果兩線段相交，則頂點數+1，但是，兩頂點可能會重合，所以必須要求出相交點的坐標。然後去掉重復的頂點，即去掉坐標值相同的頂點，那麼此時數組的大小就是V。先用sort排序，再用unique去重。 2.在求E的時候，需要對每個V中的頂點做判斷，如果點c在線段(a,b)上，不包含端點，那麼線段數目+1，求完以後，加上原來的初始化的線段數即可。 3.依據歐拉公式求F。 [cpp] #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; const double eps = 1e-8; struct Point { double x; double y; Point() {} Point(double _x,double _y):x(_x),y(_y) {} friend Point operator + (Point a,Point b) { return Point(a.x+b.x , a.y+b.y); } friend Point operator - (Point a,Point b) { return Point(a.x-b.x , a.y-b.y); } }; struct Edge { Point a; Point b; }; Edge e[315]; Point p_temp[315]; Point p[100000]; int p_num = 0; int dcmp(double x) //三態函數 { if(fabs(x)<eps)//在一定的精度范圍內可認為是0 return 0; return x>0?1:-1; } double det(Point a,Point b) // 叉積，重載叉積函數 { return a.x*b.y-a.y*b.x; } double det(Point a,Point b,Point o) // 叉積 { return det(a-o,b-o); } double det(Point a,Point b,Point c,Point d) // 叉積 { return det(b-a,d-c); } double dot(Point a,Point b) // 點積 { return a.x*b.x + a.y*b.y; } double dot(Point a,Point b,Point o) // 點積 { return dot(a-o,b-o); } void intersect(Point a,Point b,Point c,Point d)// 判斷線段是否相交 { int d1 = dcmp( det(a,b,c) ); int d2 = dcmp( det(a,b,d) ); int d3 = dcmp( det(c,d,a) ); int d4 = dcmp( det(c,d,b) ); Point temp; //求交點坐標 if((d1*d2<0&&d3*d4<0)) { double t = ((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x)); temp.x = a.x + (b.x - a.x) * t; temp.y = a.y + (b.y - a.y) * t; p[p_num++] = temp; } //c在(a,b)上 else if(d1==0&&dcmp(dot(a,b,c))<=0) { temp.x = c.x; temp.y = c.y; p[p_num++] = temp; } //d在(a,b)上 else if(d2==0&&dcmp(dot(a,b,d))<=0) { temp.x = d.x; temp.y = d.y; p[p_num++] = temp; } //a在(c,d)上 else if(d3==0&&dcmp(dot(c,d,a))<=0) { temp.x = a.x; temp.y = a.y; p[p_num++] = temp; } //b在(c,d)上 else if(d4==0&&dcmp(dot(c,d,b))<=0) { temp.x = b.x; temp.y = b.y; p[p_num++] = temp; } } //從大到小排序 bool cmp(Point a,Point b) { if(a.x - b.x >eps) { return true; } else if(fabs(a.x - b.x)<eps && a.y - b.y >eps) { return true; } return false; } //兩點坐標相等 bool cmp2(Point a,Point b) { if(fabs(a.x - b.x) < eps && fabs(a.y - b.y)<eps) { return true; } return false; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int n; int num = 0; while(scanf(" %d",&n)!=EOF && n!=0) { num++; p_num = 0; for(int i=1;i<=n;i++) { scanf(" %lf %lf",&p_temp[i].x,&p_temp[i].y); } for(int i=1;i<n;i++) { e[i].a.x = p_temp[i].x; e[i].a.y = p_temp[i].y; e[i].b.x = p_temp[i+1].x; e[i].b.y = p_temp[i+1].y; } n--; int E = n; int V = 0; for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { intersect(e[i].a,e[i].b,e[j].a,e[j].b); } } sort(p,p + p_num,cmp); p_num = unique(p,p+p_num,cmp2) - p; V = p_num; for(int i=0;i<V;i++) { for(int j=1;j<=n;j++) { //判斷頂點是否在線段上 if( dcmp(det(e[j].a,e[j].b,p[i])) == 0 && dcmp(dot(e[j].a,e[j].b,p[i]))<0 ) { E++; } } } printf("Case %d: There are %d pieces.\n",num,2+E-V); } return 0; }
