UVAlive 3263 That Nice Euler Circuit（欧拉定理）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21363

【思路】

欧拉定理:V+F-E=2。则F=E-V+2。

其中V E F分别代表平面图的顶点数，边数和面数。

涉及到判断线段是否有交点，直线求交点以及判断点是否在直线上的函数。注意求直线交点之前需要判断是否有交点，交点还需要去重。

【代码】

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define FOR(a,b,c) for(int a=(b);a<(c);a++)
 6 using namespace std;
 7 
 8 const double eps = 1e-10;
 9 int dcmp(double x) {
10     if(fabs(x)<eps) return 0; else return x<0? -1:1;
11 }
12 
13 struct Pt {
14     double x,y;
15     Pt(double x=0,double y=0):x(x),y(y) {};
16 };
17 typedef Pt vec;
18 
19 vec operator - (Pt A,Pt B) { return vec(A.x-B.x,A.y-B.y); }
20 vec operator + (vec A,vec B) { return vec(A.x+B.x,A.y+B.y); }
21 vec operator * (vec A,double p) { return vec(A.x*p,A.y*p); }
22 double Dot(vec A,vec B) { return A.x*B.x+A.y*B.y; }
23 double cross(vec A,vec B) { return A.x*B.y-A.y*B.x; }
24 bool operator < (const Pt& a,const Pt& b) {
25     return a.x<b.x || (a.x==b.x && a.y<b.y);
26 }
27 bool operator == (const Pt& a,const Pt& b) {                // for unique
28     return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
29 }
30 
31 Pt LineIntersection(Pt P,vec v,Pt Q,vec w) {
32     vec u=P-Q;
33     double t=cross(w,u)/cross(v,w);
34     return P+v*t;
35 }
36 bool SegIntersection(Pt a1,Pt a2,Pt b1,Pt b2) {
37     double c1=cross(a2-a1,b1-a1) , c2=cross(a2-a1,b2-a1) ,
38            c3=cross(b2-b1,a1-b1) , c4=cross(b2-b1,a2-b1);
39     return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
40     // b1 b2在线段a1a2的两侧  a1 a2在线段b1b2的两侧 => 规范相交
41 }
42 bool OnSeg(Pt P,Pt a1,Pt a2) {
43     return dcmp(cross(a1-P,a2-P))==0 && dcmp(Dot(a1-P,a2-P))<0;
44 }
45 
46 const int N = 300+10;
47 Pt P[N],V[N*N];
48 int n;
49 
50 int main() {
51     int kase=0;
52     while(scanf("%d",&n)==1 && n) {
53         FOR(i,0,n)
54             scanf("%lf%lf",&P[i].x,&P[i].y) , V[i]=P[i];
55         n--;
56         int c=n,e=n;
57         FOR(i,0,n) FOR(j,i+1,n)
58             if(SegIntersection(P[i],P[i+1],P[j],P[j+1]))
59                 V[c++]=LineIntersection(P[i],P[i+1]-P[i],P[j],P[j+1]-P[j]);
60         sort(V,V+c);
61         c=unique(V,V+c)-V;
62         FOR(i,0,c) FOR(j,0,n)
63             if(OnSeg(V[i],P[j],P[j+1])) e++;
64         printf("Case %d: There are %d pieces.
",++kase,e+2-c);
65     }
66     return 0;
67 }