UVA1342 That Nice Euler Circuit（ACM - ICPC 2004 Asia - Shanghai）（计算几何、欧拉定理）

欧拉定理：设平面图的顶点数、边数和面数分别为V，E，F，则V+F-E=2。

#include<bits/stdc++.h>
using namespace std;

const int N = 5007, M = 50007, INF = 0x3f3f3f3f;
const double DINF = 12345678910, eps = 1e-10;
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);}
//!点 - 点 = 向量(向量BC = C - B)
Vector operator - (Point A, Point 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, Point& b) {return a.x < b.x || (a.x == b.x && a.y < b. y);}
//!三态函数dcmp用于判断相等，减少精度问题
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) && !dcmp(a.y - b.y);}
//!求极角
//单位弧度rad
double Polar_angle(Vector A){return atan2(A.y, A.x);}
//!点积(满足交换律)
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));}
//!向量的叉积(不满足交换律)
//等于两向量有向面积的二倍(从v的方向看,w左,叉积>0,w右,叉积<0,共线,叉积=0)
//cross(x, y) = -cross(y, x)
//cross(x, y) : xAyB - xByA
double Cross(Vector A, Vector B){return A.x *  B.y - B.x * A.y;}
//!三个点确定两个向量,(交点为A的两个向量AB和AC)然后求这两个向量的叉积(叉乘)
double Area2(Point A, Point B, Point C){return Cross(B - A, C - A);}
//!一个向量旋转rad弧度之后的新向量
//!x' = xcosa - ysina, y' = xsina + ycosa
//rad:弧度
Vector Rotate(Vector A, double rad){
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
//!向量的单位法线
//实际上就是将该向量向左旋转90°
//因为是单位法线所以长度归一化
//调用前请确保A不是零向量
Vector Normal(Vector A){
    double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}


//!求两直线相交的交点
//调用前要确保两直线p + tv 和 Q + tw之间有唯一交点，当且仅当Corss(v, w) != 0;
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
	Vector u = P - Q;
	double t = Cross(w, u) / Cross(v, w);
	return P + v * t;
}

//!直线的参数式 直线 AB:A + tv(v为向量AB, t为参数)

//!点到直线的距离
double Distance_point_to_line(Point P, Point A, Point B)
{
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2) / Length(v1));//如果不取绝对值，那么得到的是有向距离
}

//!点到线段的距离
//垂线距离或者PA或者PB距离
double Distance_point_to_segment(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);//A点左边
    else if(dcmp(Dot(v1, v3)) > 0)return Length(v3);//B点右边
    else return fabs(Cross(v1, v2) / Length(v1));//垂线的距离
}

//!点在直线上的投影
//点积满足分配率:两直线垂直，点积为0，向量v,Q = A + t0v,
//点P,v与直线PQ垂直:
//Dot(v, p - (A + t0v)) = 0 -> Dot(v, P - A) - t0 * Dot(v, v) = 0;
Point Get_line_projection(Point P, Point A, Point B)
{
    Vector v = B - A;
    return A + v * (Dot(v, P - A) / Dot(v, v));
}
//!判断线段相交(端点处相交不算)
bool segment_proper_intersection(Point a1, Point a2, Point b1, Point b2)
{
    double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
    double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
//!判断点是否在一条线段上(不含端点)
bool on_segment(Point P, Point a1, Point a2)
{
    return dcmp(Cross(a1 - P, a2 - P)) == 0 && dcmp(Dot(a1 - P, a2 - P)) < 0;
}



Point p[N], v[N * N];
int n;
int kcase;
int main()
{
    while(~scanf("%d", &n) && n){
        for(int i = 0; i < n; ++ i)
            scanf("%lf %lf", &p[i].x, &p[i].y), v[i] = p[i];
        n -- ;
        int c = n, e = n;
        for(int i = 0; i < n; ++ i)
            for(int j = i + 1; j < n; ++ j)
            if(segment_proper_intersection(p[i], p[i + 1], p[j], p[j + 1]))
            //方向向量和一个点确定一个直线P =  A + tv
            v[c ++ ] = Get_line_intersection(p[i], p[i + 1] - p[i], p[j], p[j + 1] - p[j]);
        sort(v, v + c);
        c = unique(v, v + c) - v;//去重防止三点共线
        //原来有n个点，有n-1个线段，新增点以后，
        //我们看有多少个新增的点在原来的线段上，
        //每有一个在原来线段的上面就会把这个线段割开成两个线段，答案+1
        for(int i = 0; i < c; ++ i)
            for(int j = 0; j < n; ++ j)
            if(on_segment(v[i], p[j], p[j + 1]))e ++ ;
        printf("Case %d: There are %d pieces.\n", ++ kcase, e + 2 - c);
    }
    return 0;
}