That Nice Euler Circuit——Regionals 2004 >> Asia - Shanghai——UVALive - 3263

Created on November 15, 2021

2021   ·   computational geometry

一笔画，

欧拉定理：平面图的顶点数，边数和面数分别为V,E和F

则V+F-E=2，所以求出顶点数V和边数E，就可以得到F=E+2-V

V数组存在原来的结点和新增的结点，可能存在三线共点，需要删除重复的点

#include<iostream>
#include<cmath>
#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){}
};

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);
}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    return 1;
}

bool operator == (const Point& a,const Point& b)
{
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}


Point read_point()
{
    double x,y;
    cin>>x>>y;
    return Vector(x,y);
}



double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}

double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
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;
}

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);
    double c2=cross(a2-a1,b2-a1);
    double c3=cross(b2-b1,a1-b1);
    double c4=cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}

int main()
{
      int n;
    int round=1;
    while(scanf("%d",&n)== 1 && n)
    {
        Point p[310],v[90100];    
        for(int i=0;i<n;i++)
        {
                p[i]=read_point();
                v[i]=p[i];
        }
        n--;
        int c=n,e=n;
        // dian edge
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(segmentproperintersection(p[i],p[i+1],p[j],p[j+1]))
                {
                    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;
        for(int i=0;i<c;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(onsegment(v[i],p[j],p[j+1])) e++;
            }
        }
        printf("Case %d: There are %d pieces.\n",round,e-c+2);
        round++;
    }
    return 0;
}