题目链接：That Nice Euler Circuit
题意
平面上有一个包含n个端点的一笔画，第n个端点总是和第一个端点重合，因此是一条闭合的曲线。组成一笔画的线段可以相交，但是不会部分重叠。求这些线段将平面分为多少部分。
题解
欧拉定理：设平面图的顶点数、面数和边数为V、F和E，则V+F-E=2。 本题以欧拉定理为中心，若想求出F，则求出V和E即可。
先说顶点数V，首先该图形有(n-1)个顶点(本题输入时最后一个点回到第一个点所以不算)，其次计算线段两两相交的部分，由于点数最多为300，所以枚举就行。每次枚举两条线段相交于内部的点，最后排列去重就能得到总共有多少个点。
接下来说边数E，同理一开始有(n-1)条边，其次计算相交于内部的点将线段划分的线段个数，由于上面我们已经求出所有的点，那么我们只需枚举每个点在起始(n-1)条边的内部的次数，每多一次就多分了一条线段，(因为一个点能将线段分为两部分)，最后就能得出边数E。
最后答案就是F=2+E-V
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
using namespace std
;
typedef long long ll
;
typedef long double ld
;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
const double PI
=acos(-1.0);
const double eps
=1e-10;
const ll mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const int maxn
=305;
const int maxm
=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct Point
{
double x
,y
;
Point(double x
=0,double y
=0):x(x
),y(y
) { }
};
typedef Point Vector
;
Vector
operator + (Vector A
,Vector B
) { return Vector(A
.x
+B
.x
,A
.y
+B
.y
); }
Vector
operator - (Vector A
,Vector B
) { return Vector(A
.x
-B
.x
,A
.y
-B
.y
); }
Vector
operator * (Vector A
,double P
) { return Vector(A
.x
*P
, A
.y
*P
); }
bool operator < (const Point
& a
, const Point
& b
)
{
return a
.x
<b
.x
|| (a
.x
==b
.x
&& a
.y
<b
.y
);
}
int dcmp(double x
)
{
if(fabs(x
) < eps
) return 0;
else return x
<0? -1 : 1;
}
bool operator == (const Point
& a
,const Point
& b
) { return dcmp(a
.x
-b
.x
) == 0 && dcmp(a
.y
-b
.y
)==0; }
Point
read_point()
{
Point p
;
scanf("%lf%lf",&p
.x
,&p
.y
);
return p
;
}
double Dot(Vector A
,Vector B
) { return A
.x
*B
.x
+A
.y
*B
.y
; }
double Length(Vector A
) { return sqrt(Dot(A
, A
)); }
double Angle(Vector A
,Vector B
) { return acos(Dot(A
, B
) / Length(A
) / Length(B
)); }
Vector
Rotate(Vector A
,double rad
) { return Vector(A
.x
*cos(rad
)-A
.y
*sin(rad
),A
.x
*sin(rad
)+A
.y
*cos(rad
)); }
double Cross(Vector A
,Vector B
) { return A
.x
*B
.y
-A
.y
*B
.x
; }
Point
GetLine_Point(Point P
,Vector v
,Point Q
,Vector w
){
Vector u
= P
-Q
;
double t
= Cross(w
, u
) / Cross(v
, w
);
return P
+v
*t
;
}
bool SPI(Point a1
,Point a2
,Point b1
,Point b2
)
{
int c1
=dcmp(Cross(a2
-a1
, b1
-a1
)), c2
=dcmp(Cross(a2
-a1
,b2
-a1
));
int c3
=dcmp(Cross(b2
-b1
,a1
-b1
)), c4
=dcmp(Cross(b2
-b1
, a2
-b1
));
return c1
*c2
<0 && c3
*c4
<0;
}
bool Onsegment(Point p
,Point a1
,Point a2
)
{
return dcmp(Cross(a1
-p
, a2
-p
))==0 && dcmp(Dot(a1
-p
, a2
-p
))<0 ;
}
Point p
[maxn
],v
[maxn
*maxn
];
int main()
{
int n
,cas
=1;
while(scanf("%d",&n
) && n
)
{
for(int i
=1;i
<=n
;i
++) { p
[i
]=read_point(); v
[i
]=p
[i
]; }
int V
=n
-1,E
=n
-1,F
;
for(int i
=1;i
<n
;i
++)
for(int j
=i
+1;j
<n
;j
++)
{
if(SPI(p
[i
],p
[i
+1],p
[j
],p
[j
+1]))
{
v
[++V
]=GetLine_Point(p
[i
],p
[i
]-p
[i
+1],p
[j
],p
[j
]-p
[j
+1]);
}
}
sort(v
+1,v
+V
+1);
V
=unique(v
+1, v
+V
+1)-(v
+1);
for(int i
=1;i
<=V
;i
++)
{
for(int j
=1;j
<=n
;j
++)
{
if(Onsegment(v
[i
],p
[j
],p
[j
+1])) E
++;
}
}
printf("Case %d: There are %d pieces.\n",cas
++,2+E
-V
);
}
}
