POJ 2284 That Nice Euler Curcuit（LA 3263 HDU 1665）

http://poj.org/problem?id=2284
https://icpcarchive.ecs.baylor.edu/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&problem=1264
http://acm.hdu.edu.cn/showproblem.php?pid=1665
タイトルの大意:
平面にはn個の端点を含む一画があり、n番目の端点は常に最初の端点と重なるため、パターンは閉じた曲線である。一画の線分を作ると交わることができますが、重なり合うことはありません。これらの線分を求めて、平面をいくつかの部分に分けます。
考え方:
劉汝佳の本の上の原題。彼を基本的に写して、幾何問題かは経験していません。uniqueの使い方も学びました。隣接している同じ元素を取り除きます。
オーラの定理は平面図の一番上の点数、辺の数を設定してそれぞれV、E、FはV+F-E=2です。（前学期に勉強したばかりの離散数学は今勉強して売ります。）
上の図のように、右のE=12、V=9、F=5.
平面図の結点は、元の頂点と新たに増加した頂点の2つの部分からなります。3点の共通線がありますので、重複点を削除します。

#include<cstdio>
#include<cmath>
#include<algorithm>
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<b.x||a.x==b.x && a.y<b.y;
}
bool operator ==(const Point &a,const Point &b)
{
	return a.x==b.x && a.y==b.y;
}
Point v[MAXN*MAXN],p[MAXN];
int main()
{
	int n,kase=1;
	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];
		}

		int len=n--,e=n;
		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[len++]=GetLineIntersection(p[i],p[i+1]-p[i],p[j],p[j+1]-p[j]);
			}

		sort(v,v+len);
		int c=unique(v,v+len)-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++;

		//v+f-e=2 f=e+2-v
		printf("Case %d: There are %d pieces.
",kase++,e+2-c);
	}
	return 0;
}