POJ 2284 That Nice Euler Circuit (LA 3263 HDU 1665)

http://poj.org/problem id=2284

https://icpcarchive.ecs.baylor.edu/index.php option=com_onlinejudge&Itemid=8&page=show_problem&problem=1264

http://acm.hdu.edu.cn/showproblem.php pid=1665

题目大意：

平面上有一个包含n个端点的一笔画，第n个端点总是和第一个端点重合，因此图案是一条闭合的曲线。组成一笔画的线段可以相交，但是不会重合。求这些线段将平面分成多少部分。

思路：

刘汝佳书上原题。我基本抄他的，几何题没经验T T。还学到了unique的用法，去除相邻相同的元素

欧拉定理有：设平面图的顶点数、边数、面数分别V,E,F则V+F-E=2（上个学期刚学的离散数学，现学现卖啊！）

如上面的图，右边的E=12,V=9,F=5.

平面图的结点由两部分组成，即原来顶点和新增加的顶点，因为可能出现三点共线，所以要删除重复点。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=300+10; const double eps = 1e-10; int dcmp(double x) //判断浮点数是否等于0，或者小于大于0 { if(fabs(x) < eps) return 0; else return x < 0   -1 : 1; } struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { } }; typedef Point Vector; Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } //两直线交点，参数式。 Point GetLineIntersection(const Point& P, const Vector& v, const Point& Q, const Vector& w) { Vector u = P-Q; double t = Cross(w, u) / Cross(v, w); return P+v*t; } //两直线是否有交点，两点式。 bool SegmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const 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; } //点在线段上的判定，两点式 bool OnSegment(const Point& p, const Point& a1, const Point& a2) { return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) < 0; } bool operator <(const Point &a,const Point &b) { return a.x