学步园

给一个闭合的区间，求围成的区域的个数。

根据欧拉定理 顶点数-棱边数+面数=2

顶点数就是把所有交点求出来再跟原有顶点放一起去重，

棱边数就是考虑某一条原有的边，在这条边上的点为x个，那么这条边的棱边数就是x-1条，

n-1条边就是sum(x)-n+1条，所以答案就是sum(x)-n+1-top+2个面。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
using namespace std ;
typedef long long ll ;
const int maxint = (1<<30)-1 ;
const double eps = 1e-6 ;
const double pi = 3.141592653589793238462;
const int mod = 1000000007;
const int MAX = 510;
struct point{
    double x,y,ang;
    point(){};
    point(double xx,double yy){x=xx,y=yy;}
    void pr(){
        printf("%.2lf %.2lf\n",x,y);
    }
}p[310],t[100010];
int cmp(double x){
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}
bool operator ==(point a,point b){
    return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
bool operator <(point a,point b){
    if(cmp(a.x-b.x))return a.x<b.x;
    return a.y<b.y;
}
point operator -(point a,point b){
    return point(a.x-b.x,a.y-b.y);
}
point operator *(point a,double b){
    return point(a.x*b,a.y*b);
}
point operator /(point a,double b){
    return point(a.x/b,a.y/b);
}
double dot(point a,point b){
    return a.x*b.x+a.y*b.y;
}
double det(point a,point b){
    return a.x*b.y-a.y*b.x;
}
bool parallel(point aa,point ab,point ba,point bb){
    return !cmp(det(aa-ab,ba-bb));
}
bool onseg(point p,point s,point t){
    return cmp(det(p-s,t-s))==0&&cmp(dot(p-s,p-t))<=0;
}
bool jiaodian(point aa,point ab,point ba,point bb,point& as){
    if(parallel(aa,ab,ba,bb))return 0;
    double s1=det(aa-ba,bb-ba);
    double s2=det(ab-ba,bb-ba);
    as=(ab*s1-aa*s2)/(s1-s2);
    return 1;
}
int main(){
    int i,j,n,m,top,as,cs=1;
    point tmp;
    while(scanf("%d",&n),n){
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        top=0;
        for(i=1;i<n;i++)
            for(j=i+1;j<n;j++){
                if(jiaodian(p[i],p[i-1],p[j],p[j-1],tmp)&&
                   onseg(tmp,p[i],p[i-1])&&onseg(tmp,p[j],p[j-1]))
                    t[top++]=tmp;
            }
        for(i=0;i<n;i++)t[top++]=p[i];
        sort(t,t+top);
        top=unique(t,t+top)-t;
        as=0;
        for(i=1;i<n;i++)
            for(j=0;j<top;j++)
                if(onseg(t[j],p[i],p[i-1]))
                    as++;
        printf("Case %d: There are %d pieces.\n",cs++,as-n-top+3);
    }
    return 0;
}