zoj 1460 The Partition of a Cake

入力坑姐啊!!!
離散数学上の図論の方法を採用しているので,つまり類似している.http://blog.csdn.net/zxy_snow/article/details/65814745この問題の方法、これはケーキの塊の数を求めて、つまりこの平面図の面の数-1.
Eulerの定理によれば,連通平面図(交点をすべて接点と見なせば,平面図に違いない)はV−E＋R＝2を満たす.ここで、Vは頂点数、Eは辺数、Rは面数である.
だから直接すべての交点を探して(缲り返すことができなくて、私は下の顺に并んで重さを取り除きます)、辺の数を探して、図を描いて知ることができて、1本の線分の上でNつの交点があって、それではN-1部に分けられました~だからこのように探せばいいです(この点はすべての線分が重ならないようにしなければなりません~!).
ゞ坑姐啊!!!ゞタイトル上、The intersections of the cut line and the cake edge are two.入力データはいずれもセグメントがエッジに2点あるので、セグメントの2つの端点は矩形のエッジにある==に違いないと思います.さっきテストしましたが、端にいなければ、プログラムにwhile(1)を実行させます.結果は本当にTLEで、データ線分の2点が辺にないかもしれないことを説明して、坑姉さん!!では、交点を計算するときは、この交点がこの矩形内(境界を含む)にあるかどうかを判断しなければなりません.
もう一つ注意したいのは、切れ目が重なっている可能性があるので、切れ目が発生したことがあるかどうか==を判断しなければなりません..また、切れ目の端点が勝手に与えられているので、共線==であるか否かを判断し、等しいか否かを判断しない(私は等しいか否かを判断していないが、試しただけで、その中に重複切れ目があるに違いない!)
もう一つの方法は、青い本の上で、http://blog.csdn.net/program_shun/article/details/6589452とこの問題解の差は少ないでしょうが、青い本には証明があります.(『実用アルゴリズム分析設計』).
ちょうど自分の书いた重さを取り除くプログラムを削除して、uniqueの関数を使って、とても便利ですね、uniqueは隣接して缲り返す要素を除いて1つ残すことしかできなくて、だから必ず顺番を决めてからuniqueを使って、uniqueの比较の関数を书いて、これも比较的に便利ですね、STLは伟大です~~

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;

const int MAX = 10;
struct point{ double x,y;};
const double eps = 1e-8;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double crossProduct(point a,point b,point c)//   ac   ab     
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
point p[MAX*MAX];
struct line{ point a,b; 
			void p(double x,double y,double x1,double y1)
			{
				a.x = x; a.y = y;
				b.x = x1; b.y = y1;
			}
};
line l[MAX];
int ee;
bool cmp(point a,point b)
{
	if( dd(a.x,b.x) ) return xy(a.y,b.y);
	return xy(a.x,b.x);
}
bool cmp1(point a,point b)
{
	return dd(a.x,b.x) && dd(a.y,b.y);
}
bool onSegment(point a, point b, point c)
{
	double maxx = max(a.x,b.x);
	double maxy = max(a.y,b.y);
	double minx = min(a.x,b.x);
	double miny = min(a.y,b.y);
	if( dd(crossProduct(a,b,c),0.0) && dyd(c.x,minx) && xyd(c.x,maxx) && dyd(c.y,miny) && xyd(c.y,maxy) )
		return true;
	return false;
}
bool s2s_inst(point p1,point p2, point p3, point p4) 
{
	double d1 = crossProduct(p3,p4,p1);
	double d2 = crossProduct(p3,p4,p2);
	double d3 = crossProduct(p1,p2,p3);
	double d4 = crossProduct(p1,p2,p4);
	if( xy(d1 * d2,0.0) && xy(d3 * d4,0.0) )	return true;
	if( dd(d1,0.0) && onSegment(p3,p4,p1) )		return true;//        ，           
	if( dd(d2,0.0) && onSegment(p3,p4,p2) )		return true;
	if( dd(d3,0.0) && onSegment(p1,p2,p3) )		return true;
	if( dd(d4,0.0) && onSegment(p1,p2,p4) )		return true;
	return false;
}
point s2s_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
void check(point x,int n)
{
	for(int i=0; i<n; i++)
		if( onSegment(l[i].a,l[i].b,x) )
			ee++;
}
bool chong(point a,point b,int n)
{
	for(int i=0; i<n; i++)
		if( dd(crossProduct(l[i].a,l[i].b,a),0.0) 
			&& dd(crossProduct(l[i].a,l[i].b,b),0.0) )
			return true;
	return false;
}
int main()
{
	l[0].p(0,0,1000,0); l[1].p(0,0,0,1000); 
	l[2].p(0,1000,1000,1000); l[3].p(1000,0,1000,1000);
	
	int n;
	double a,b,c,d;
	while( ~scanf("%d",&n) && n )
	{
		int cnt = 0;
		ee = 0;
		int cc = 4;
		while( n-- )
		{
			scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
			point aa,bb; aa.x = a; aa.y = b; bb.x = c; bb.y = d;
			if( !chong(aa,bb,cc) )
				l[cc++].p(a,b,c,d);
		} 
		n = cc;	
		for(int i=0; i<n; i++)
			for(int k=i+1; k<n; k++)
				if( s2s_inst(l[i].a,l[i].b,l[k].a,l[k].b) )
				{
					point pp = s2s_inst_p(l[i].a,l[i].b,l[k].a,l[k].b);
					if( dyd(pp.x,0.0)  && xyd(pp.x,1000.0) && dyd(pp.y,0.0) && xyd(pp.y,1000.0) )
						p[cnt++] = pp;
				}

		sort(p,p+cnt,cmp);
		int nn = unique(p,p+cnt,cmp1) - p;// unique     ~~ 
		
		for(int i=0; i<nn; i++)
			check(p[i],n);	//       
			
		int ans = ee - n - nn + 1;
		printf("%d
",ans);
	}

return 0;
}