链接：

id=2284">http://poj.org/problem?id=2284

题意：一个自己主动绘图的机器在纸上（无限大）绘图，笔尖从不离开纸，有n个指令，每一个指令是一个坐标，由于笔尖不离开纸，所以相邻的坐标会连有一条直线，最后画笔再回到起始点。

所以这个图是一个连通图，而且画笔走过的路径是一个欧拉回路。

如今问题来了。这个图形将平面分成了几部分。

思路：题目说明确一些就是告诉你一些几何信息问平面被分成了几部分。能够用欧拉公式来做

欧拉公式：如果图的顶点个数为n，边数为m，区域数位r，则有 n - m + r = 2，前提必须是连通图

知道随意两个就能求第三个

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 90010

#define eps 1e-7

#define INF 0x3F3F3F3F      //0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 1313131

#define MOD 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct Point{   //点

    double x, y;

    Point(double a = 0, double b = 0){

        x = a;

        y = b;

    }

};

struct LineSegment{ //线段

    Point s, e;

    LineSegment(Point a, Point b){

        s = a;

        e = b;

    }

};

struct Line{    //直线

    double a, b, c;

};

bool operator < (Point p1, Point p2){

    return (p1.x < p2.x || p1.x == p2.x) && p1.y < p2.y;

}

bool operator == (Point p1, Point p2){

    return fabs(p1.x - p2.x) < eps && fabs(p1.y - p2.y) < eps;

}

bool Online(LineSegment l, Point p){    //推断点是否在线段上

    return fabs((l.e.x - l.s.x) * (p.y - l.s.y) - (p.x - l.s.x) * (l.e.y - l.s.y)) < eps

        && (p.x - l.s.x) * (p.x - l.e.x) < eps && (p.y - l.s.y) * (p.y - l.e.y) < eps;

}

Line MakeLine(Point p1, Point p2){  //将线段延长为直线

    Line l;

    if(p2.y > p1.y){

        l.a = p2.y - p1.y;

        l.b = p1.x - p2.x;

        l.c = p1.y * p2.x - p1.x * p2.y;

    }

    else{

        l.a = p1.y - p2.y;

        l.b = p2.x - p1.x;

        l.c = p1.x * p2.y - p1.y * p2.x;

    }

    return l;   //返回直线

}

bool LineIntersect(Line l1, Line l2, Point &p){ //推断直线是否相交。并求出交点p

    double d = l1.a * l2.b - l2.a * l1.b;

    if(fabs(d) < eps) return false;

    //求交点

    p.x = (l2.c * l1.b - l1.c * l2.b) / d;

    p.y = (l2.a * l1.c - l1.a * l2.c) / d;

    return true;

}

bool LineSegmentIntersect(LineSegment l1, LineSegment l2, Point &p){    //推断线段是否相交

    Line a, b;

    a = MakeLine(l1.s, l1.e), b = MakeLine(l2.s, l2.e); //将线段延长为直线

    if(LineIntersect(a, b, p))  //假设直线相交

        return Online(l1, p) && Online(l2, p);  //推断直线交点是否在线段上，是则线段相交

    else

        return false;

}

bool cmp(Point a, Point b){

    if(fabs(a.x - b.x) < eps)   return a.y < b.y;

    else    return a.x < b.x;

}

Point p[MAXN], Intersection[MAXN];

int N, m, n;

int main(){

    int i, j, cas = 1;

    while(scanf("%d", &N), N){

        m = n = 0;

        for(i = 0; i < N; i++){

            scanf("%lf%lf", &p[i].x, &p[i].y);

        }

        for(i = 0; i < N; i++){

            for(j = 0; j < N; j++){

                LineSegment l1(p[i], p[(i + 1) % N]), l2(p[j], p[(j + 1) % N]);

                Point p;

                if(LineSegmentIntersect(l1, l2, p))

                    Intersection[n++] = p;  //记录交点

            }

        }

        sort(Intersection, Intersection + n, cmp);

        n = unique(Intersection, Intersection + n) - Intersection;

        for(i = 0; i < n; i++){

            for(j = 0; j < N; j++){

                LineSegment t(p[j], p[(j + 1) % N]);

                if(Online(t, Intersection[i]) && !(t.s == Intersection[i]))  //若有交点落在边上，则该边分裂成两条边

                    m++;

            }

        }

        printf("Case %d: There are %d pieces.\n", cas++, 2 - n + m);

    }

    return 0;

}