欧拉定理：V为平面图定点数，E为平面边数，F为平面区域数，则V+F-E=2;
题意：平面上有一个包含n个端点的一笔画，第n个端点总是和第一个端点重合，图案是一条闭合曲线，组成一笔画的线段可以相交，但是不会不分重叠，求这些线段将平面分为多少部分。
题解：平面的节点由原来的节点和相交得到的新节点组成，有可能出现重复计数的交点，即三线共点，需要去重。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<complex>
#define maxn 305
using namespace std;
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);}
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);
}
const double eps=1e-10;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
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;
}
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)) ;}
double cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A,Point B,Point C){return cross(B-A,C-A);}
Vector rorate(Vector A,double rad)
{
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
Vector normal(Vector A)//左转90du，单位向量
{
double L=length(A);
return Vector(-A.y/L,A.x/L);
}
Point getLineIntersection(Point P,Vector v,Point Q,Vector w)//两直线的交点
{
Vector u=P-Q;
double t=cross(w,u)/cross(v,w);
return P+v*t;
}
double distanceToLine(Point P,Point A,Point B)//点到直线距离
{
Vector v1=B-A,v2=P-A;
return fabs(cross(v1,v2))/length(v1);
}
double distanceToSegment(Point p,Point A,Point B)
{
if(A==B) return length(p-A);
Vector v1=B-A,v2=p-A,v3=p-B;
if(dcmp(dot(v1,v2))<0) return length(v2);
else if(dcmp(dot(v1,v3))>0) return length(v3);
else return fabs(cross(v1,v2))/length(v1);
}
Point getLineProjection(Point P,Point A,Point B)//p点在AB直线上的投影
{
Vector v=B-A;
return A+v*(dot(v,P-A)/dot(v,v));
}
bool segmentProperIntersection(Point a1,Point a2,Point b1,Point 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)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool onSegment(Point p,Point a1,Point a2)//p点是否在线段上，不包括a1，a2
{
return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
}
double convexPolygonArea(Point *arr,int n)//计算多边形面积
{
double area=0.0;
for(int i=1;i<n-1;i++)
{
area+=cross(arr[i]-arr[0],arr[i+1]-arr[0]);
}
return fabs(area/2);
}
double PolygonArea(Point *arr,int n)//计算多边形有向面积
{
double area=0.0;
for(int i=1;i<n-1;i++)
{
area+=cross(arr[i]-arr[0],arr[i+1]-arr[0]);
}
return area/2;
}
int main()
{
Point p[maxn*maxn],arr[maxn];
int n,t=1,v,e;
while(scanf("%d",&n)==1,n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
arr[i]=p[i];
}
n--;
v=n;
e=n;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(segmentProperIntersection(arr[i],arr[i+1],arr[j],arr[j+1]))//规范相交
p[v++] =getLineIntersection(arr[i],arr[i+1]-arr[i],arr[j],arr[j+1]-arr[j]);//求交点
}
}
sort(p,p+v);
v=unique(p,p+v)-p;//unique可以去重，但不会删除元素，只是把重复的元素放到数组后面，函数返回第一个重复元素的指针
for(int i=0;i<v;i++)
{
for(int j=0;j<n;j++)
{
if(onSegment(p[i],arr[j],arr[j+1])) e++;//如果是新增的节点，那么它一定在原来的线段上面，则e++
}
}
printf("Case %d: There are %d pieces.\n",t++,2+e-v);
}
}
