UVALive-3263 That Nice Euler Circuit （几何欧拉定理）

https://vjudge.net/problem/UVALive-3263

 

平面上有一个n个端点的一笔画，第n个端点总是和第一个端点重合，因此图示一条闭合曲线。

组成一笔画的线段可以相交，但不会部分重叠，求这些线段将平面分为几部分

包括封闭区域和无限大区域

 

欧拉定理：平面图的顶点数V，边数E，面数F ，V+F-E=2

顶点数包含原来节点、新增节点，可能多线共点，所以还要去重

边数包含原来的边、新增的边，

判断新增边：枚举点、边，如果点在线段上（非端点处），边数+1

判断点在线段上且非端点：点与线段端点两向量的叉积=0，点积<0

（如果是端点点积=0）

#include<cmath>
#include<cstdio>
#include<algorithm>

using namespace std;

const double eps=1e-10;

struct Point
{
    double x,y;
    Point(double x=0,double y=0) : x(x),y(y) { }
    bool operator == (const Point b) const
    {
        return fabs(x-b.x)<eps && fabs(y-b.y)<eps; 
    }
    bool operator < (const Point b) const
    {
        return (x<b.x||(fabs(x-b.x)<eps && y<b.y));
    }
    /*Point operator = (const Point b)
    {
        return b;        
    }*/
};

typedef Point Vector;


Point p[301],section[90301];

int sumedge,sumpoint;

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); }

struct Geometry
{
    double Cross(Vector A,Vector B)
    {
        return A.x*B.y-A.y*B.x;
    }
    double Dot(Vector A,Vector B)
    {
        return A.x*B.x+A.y*B.y;
    }
    bool OnSegment(Point p,Point a1,Point a2)
    {
        return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<0;
    }
    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;
    }
    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;
    }
    int dcmp(double x)
    {
        if(fabs(x)<eps) return 0; return x<0 ? -1:1;
    }
};

Geometry Two_dimensional;


/*bool operator == (Point a,Point b)
{
    return Two_dimensional.dcmp(a.x-b.x)==0 && Two_dimensional.dcmp(a.y-b.y)==0; 
}
bool operator < (Point a,Point b)
{
    if(Two_dimensional.dcmp(a.x-b.x)==0)
    {
        if(Two_dimensional.dcmp(a.y-b.y)<=0) return 1;
        return 0;
    }
    if(Two_dimensional.dcmp(a.x-b.x)==-1) return 1;
    return 0;
}*/

/*bool operator < (const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool operator == (const Point& a, const Point& b) 
{
    return Two_dimensional.dcmp(a.x - b.x) == 0 && Two_dimensional.dcmp(a.y - b.y) == 0;
}*/ 
int main()
{
    int n,k,tt=0;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) return 0;
        for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y),section[i]=p[i];
        n--;
        sumpoint=n; sumedge=n;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
             {
                if(Two_dimensional.SegmentProperIntersection(p[i],p[i+1],p[j],p[j+1]))  
                    section[sumpoint++]=Two_dimensional.GetLineIntersection(p[i],p[i+1]-p[i],p[j],p[j+1]-p[j]);
             }
        sort(section,section+sumpoint);
        sumpoint=unique(section,section+sumpoint)-section;
        //for(int i=0;i<sumpoint;i++) printf("%.5lf %.5lf\n",section[i].x,section[i].y);
        for(int i=0;i<sumpoint;i++)
         for(int j=0;j<n;j++)
          if(Two_dimensional.OnSegment(section[i],p[j],p[j+1])) sumedge++;
        printf("Case %d: There are %d pieces.\n",++tt,sumedge+2-sumpoint);
    }
    
}