1921.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"

/////////////////////////
#define Type double /*坐标类型*/
/////////////////////////
const double eps=0.0001;

struct point
{Type x,y;
point(){x=y=0;}
point(Type x,Type y):x(x),y(y){;}
bool operator==(point &a){return fabs(x-a.x)<eps&&fabs(y-a.y)<eps;}
};

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

double jl(point &a,point &b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

const double pi=3.14159265359;

inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}

////////////////////////////////////////////
//求交点
//判断l1,l2不重合 先!!!

point crosspoint(line l1,line l2)
{Type p1=cheng(l2.a,l1.a,l2.b),
p2=cheng(l2.a,l2.b,l1.b);
if(p1+p2==0)return l1.a;

point c;
c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
return c;
}
////////////////////////////////////////////////


inline point pingyi(point p,point o)
{
	point c;
	c.x=p.x-o.x;
	c.y=p.y-o.y;
	
	return c;
}

inline point fanshe(point p,double sina,double cosa)
{
	point c;
	double cos2a=cosa*cosa-sina*sina;
	double sin2a=2*sina*cosa;

	c.x=cos2a*p.x+sin2a*p.y;
	c.y=sin2a*p.x-cos2a*p.y;

	return c;
}

struct newline:public line
{
	
	double sina,cosa;
};

inline point zhedie(point p,newline l)
{
	point c;
	c=fanshe(pingyi(p,l.a),l.sina,l.cosa);
	c.x+=l.a.x;
	c.y+=l.a.y;
	return c;
}

newline zhe[21];

struct plane
{
	point d[100];
	int n;
	int from,xian;
	bool flag;
};

plane p[1000];
int pn;

void zhezhi()
{
	int n,i,j,t,k,h;
	newline z;
	double s;point a,b;
	bool set[100],key;
	
	cin>>n;
	
	for(k=0;k<n;k++)
	{
		cin>>z.a.x>>z.a.y>>z.b.x>>z.b.y;
		s=jl(z.a,z.b);
		z.sina=(z.b.y-z.a.y)/s;
		z.cosa=(z.b.x-z.a.x)/s;
		
		t=pn;
		for(i=0;i<t;i++)
		if(p[i].flag)
		{
			key=0;
			for(j=0;j<p[i].n;j++)
			{
				if(cheng(p[i].d[j],z.a,z.b)>0){set[j]=1;key=1;}
				else set[j]=0;
			}

			if(key)
			{
				p[i].flag=0;
				
				for(j=0;j<p[i].n;j++)
					if(!set[j]&&set[(j+1)%p[i].n])
						break;

				if(j==p[i].n)
				{
					p[pn].flag=1;
					p[pn].from=i;
					p[pn].xian=k;
					p[pn].n=p[i].n;
					
					for(h=0;h<p[i].n;h++)
						p[pn].d[h]=zhedie(p[i].d[h],z);

					pn++;
				}
				else
				{
					a=crosspoint(line(p[i].d[j],p[i].d[(j+1)%p[i].n]),z);

					p[pn].flag=1;
					p[pn].from=i;
					p[pn].xian=k;
					p[pn].d[0]=a;
					
					for(p[pn].n=1;set[(j+1)%p[i].n];j++)
					{
						p[pn].d[p[pn].n++]=zhedie(p[i].d[(j+1)%p[i].n],z);
					}
					
					b=crosspoint(line(p[i].d[j%p[i].n],p[i].d[(j+1)%p[i].n]),z);
					
					p[pn].d[p[pn].n++]=b;

					pn++;
					p[pn].flag=1;
					p[pn].from=p[i].from;
					p[pn].xian=p[i].xian;
					
					p[pn].d[0]=b;

					for(p[pn].n=1;!set[(j+1)%p[i].n];j++)
					{
						p[pn].d[p[pn].n++]=p[i].d[(j+1)%p[i].n];
					}
					
					p[pn].d[p[pn].n++]=a;

					pn++;
				}
			}
		}//for
	
		zhe[k]=z;
	
	}
	return ;
}
//////////////////////////////////////////////////////////////////////////////
point cut[1000][2];
int cuts;

void cutit()
{
	line cutline;
	int i,j,c,from;
	bool set[100];
	
	cin>>cutline.a.x>>cutline.a.y>>cutline.b.x>>cutline.b.y;

	for(i=0;i<pn;i++)
	if(p[i].flag)
	{
		for(j=0;j<p[i].n;j++)
		{
			if(cheng(p[i].d[j],cutline.a,cutline.b)>=0)set[j]=1;
			else set[j]=0;
		}
		
		c=0;
		for(j=0;j<p[i].n;j++)
		{
			if(set[j]!=set[(j+1)%p[i].n])
			{
				if(cheng(p[i].d[j],cutline.a,cutline.b)==0&&
					(	cheng(p[i].d[(j+1)%p[i].n],cutline.a,cutline.b)==0 ||
						cheng(p[i].d[(j-1+p[i].n)%p[i].n],cutline.a,cutline.b)==0 ) )
						int *pdd=new int[1000000000];
			
				cut[cuts][c++]=crosspoint(line(p[i].d[j],p[i].d[(j+1)%p[i].n]),cutline);
			}
		}

		if(c==2)
		{
			for(from=i;p[from].xian>=0;from=p[from].from)
			{
				cut[cuts][0]=zhedie(cut[cuts][0],zhe[p[from].xian]);
				cut[cuts][1]=zhedie(cut[cuts][1],zhe[p[from].xian]);
			}
			cuts++;
		}
	}

}

void init()
{
	cuts=0;
	
	point a(0,0);	point b(0,1);	point c(1,1);	point d(1,0);


	pn=1;
	p[0].flag=1;
	p[0].from=-1;
	p[0].xian=-1;
	p[0].n=4;	p[0].d[0]=a;	p[0].d[1]=b;	p[0].d[2]=c;	p[0].d[3]=d;
	
	return ;
}

bool sign[1000],flag[1000];
bool map[1000][1000];
int m,ring;
point d[1000];


bool noline(point a,point b)
{
	if(a.x==b.x&&fabs(a.x-1)<eps)return 0;
	if(a.x==b.x&&a.x<eps)return 0;
	if(a.y==b.y&&fabs(a.y-1)<eps)return 0;
	if(a.y==b.y&&a.y<eps)return 0;
	return 1;
}

void find(int a)
{
	int i;
	flag[a]=1;
	for(i=0;i<m;i++)
		if(map[a][i]&&!flag[i])find(i);

	return;
}



void count()
{
	int i,a,b,j,e;
	m=0;

	for(i=0;i<cuts*2;i++)
	for(j=0;j<cuts*2;j++)
		map[i][j]=0;

	for(i=0;i<cuts;i++)
	{
		for(a=0;a<m;a++)
			if(d[a]==cut[i][0])break;
		
		if(a==m)d[m++]=cut[i][0];

		for(b=0;b<m;b++)
			if(d[b]==cut[i][1])break;
		
		if(b==m)d[m++]=cut[i][1];

		map[a][b]=map[b][a]=1;
	}
	
	e=0;
	for(i=0;i<m;i++)
		if(fabs(d[i].x-1)<eps||fabs(d[i].y-1)<eps||d[i].x<eps||d[i].y<eps)
		{
			sign[i]=1;
			e++;
		}
		else sign[i]=0;

	for(i=0;i<m;i++)
	for(j=i+1;j<m;j++)
	{
		if(map[i][j]&&(sign[i]==0||sign[j]==0||noline(d[i],d[j]) ))
			e++;
	}

	for(i=0;i<m;i++)flag[i]=0;
	
	for(i=0;i<m;i++)
	if(sign[i]==1&&!flag[i])find(i);

	ring=e+2-m-1;

	for(i=0;i<m;i++)
	if(!flag[i])
	{
		ring++;
		find(i);
	}
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		init();
		zhezhi();
		cutit();
		count();
		cout<<ring<<endl;
	}
	return 0;
}