《训练指南》—

《训练指南》——8.3

LA3263：

题目大意：给出一个一笔画图形，它包含n个点。先给出其n个点坐标之后，求解这个图形把平面分成了几个区域。

分析：这里要求的是面的个数，显然连直接暴力进行求解的方法都没有，因此这里就需要进行一定的转化，已知信息是点的坐标，那么我们应该能够想到平面几何中的欧拉定理(我们将图形看成图论当中的图G)，经过这一步转换，我们需要做的就是求解图形的点数和边数。

点：显然这里我们就需要设置暴力，以确保能够完成所有相交情况的筛查。穷举之后，原来的节点数加交点数(去重后)就是该图中的总结点数v.

边：结合欧拉定理的适用条件，这里需要注意的是“边”的两个节点的直接连线。

简单的参考代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const double eps = 1e-8;

int dcmp(double x){if(fabs(x)<eps) return 0; return (x<0)?-1:1;}

struct Point
{
    double x,y;
    Point(double _x=0,double _y=0):x(_x),y(_y){};
};

Point operator+(Point A,Point B) {return Point(A.x+B.x,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 p) {return Point(A.x*p,A.y*p);}
Point operator/(Point A,double p) {return Point(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);}
bool operator==(const Point&a,const Point&b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}

double Dot(Point A,Point B) {return A.x*B.x+A.y*B.y;}  //点积
double Cross(Point A,Point B) {return A.x*B.y-A.y*B.x;} //叉积

//P+tv和Q+tw的交点
Point GetLineIntersection(Point P,Point v,Point Q,Point w)
{
    Point u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}

//判断规范相交
bool SegmentProperIntersection(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;
}

//判断点p是否在线段a1a2上
bool OnSegment(Point p,Point a1,Point a2)
{
    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}

int n;
Point pt[1000];
vector<Point> vp;

int main()
{
    int cas=1;
    while(scanf("%d",&n)!=EOF&&n)
    {
        vp.clear();
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&pt[i].x,&pt[i].y);
            vp.push_back(pt[i]);
        }
        n--;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(SegmentProperIntersection(pt[i],pt[i+1],pt[j],pt[j+1]))
                {
                    vp.push_back(GetLineIntersection(pt[i],pt[i+1]-pt[i],pt[j],pt[j+1]-pt[j]));
                }
            }
        }
        sort(vp.begin(),vp.end());
        int c=unique(vp.begin(),vp.end())-vp.begin();
        int e=n;
        int cc=0;
        for(vector<Point>::iterator it=vp.begin();cc<c&&it!=vp.end();cc++,it++)
        {
            for(int i=0;i<n;i++)
            {
                if(OnSegment(*it,pt[i],pt[i+1])) e++;
            }
        }
        printf("Case %d: There are %d pieces.
",cas++,e+2-c);
    }
    return 0;
}

看完代码读者可能会疑惑，这里求解交点真的可以用简单的规范相交吗？我们不要忘记了规范相交的定义，只要交点不是端点的情况，都是可以用规范相交的方法表示的，这里我们计算节点数已经单独将端点拿出，因此用规范相交判断相交并计数的正确的。