题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21363
【思路】
欧拉定理:V+F-E=2。则F=E-V+2。
其中V E F分别代表平面图的顶点数,边数和面数。
涉及到判断线段是否有交点,直线求交点以及判断点是否在直线上的函数。注意求直线交点之前需要判断是否有交点,交点还需要去重。
【代码】
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<(c);a++)
using namespace std; const double eps = 1e-;
int dcmp(double x) {
if(fabs(x)<eps) return ; else return x<? -:;
} struct Pt {
double x,y;
Pt(double x=,double y=):x(x),y(y) {};
};
typedef Pt vec; vec operator - (Pt A,Pt B) { return vec(A.x-B.x,A.y-B.y); }
vec operator + (vec A,vec B) { return vec(A.x+B.x,A.y+B.y); }
vec operator * (vec A,double p) { return vec(A.x*p,A.y*p); }
double Dot(vec A,vec B) { return A.x*B.x+A.y*B.y; }
double cross(vec A,vec B) { return A.x*B.y-A.y*B.x; }
bool operator < (const Pt& a,const Pt& b) {
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
bool operator == (const Pt& a,const Pt& b) { // for unique
return dcmp(a.x-b.x)== && dcmp(a.y-b.y)==;
} Pt LineIntersection(Pt P,vec v,Pt Q,vec w) {
vec u=P-Q;
double t=cross(w,u)/cross(v,w);
return P+v*t;
}
bool SegIntersection(Pt a1,Pt a2,Pt b1,Pt b2) {
double c1=cross(a2-a1,b1-a1) , c2=cross(a2-a1,b2-a1) ,
c3=cross(b2-b1,a1-b1) , c4=cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)< && dcmp(c3)*dcmp(c4)<;
// b1 b2在线段a1a2的两侧 a1 a2在线段b1b2的两侧 => 规范相交
}
bool OnSeg(Pt P,Pt a1,Pt a2) {
return dcmp(cross(a1-P,a2-P))== && dcmp(Dot(a1-P,a2-P))<;
} const int N = +;
Pt P[N],V[N*N];
int n; int main() {
int kase=;
while(scanf("%d",&n)== && n) {
FOR(i,,n)
scanf("%lf%lf",&P[i].x,&P[i].y) , V[i]=P[i];
n--;
int c=n,e=n;
FOR(i,,n) FOR(j,i+,n)
if(SegIntersection(P[i],P[i+],P[j],P[j+]))
V[c++]=LineIntersection(P[i],P[i+]-P[i],P[j],P[j+]-P[j]);
sort(V,V+c);
c=unique(V,V+c)-V;
FOR(i,,c) FOR(j,,n)
if(OnSeg(V[i],P[j],P[j+])) e++;
printf("Case %d: There are %d pieces.\n",++kase,e+-c);
}
return ;
}