1774.txt

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

#include"iostream.h"


struct point
{double x,y;};
struct line
{point a,b;};

point a[1010],b[1010];
 int n,d[1010];


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

inline double dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
///////////////
void init()
{int i;
d[0]=-1;
a[0].x=0;b[0].x=0;
a[0].y=1;b[0].y=0;

for(i=1;i<=n;i++)
{cin>>a[i].x>>b[i].x>>d[i];a[i].y=1;b[i].y=0;}

}
/////////////////////////////////////
int jiao(line l1,line l2)
{double s1=cheng(l1.a,l1.b,l2.a),
	s2=cheng(l1.a,l1.b,l2.b),s3,s4;
	if(s1*s2>0)return 0;
	s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);
	if(s3*s4>0)return 0;
	if(s1*s2<0&&s3*s4<0)return 1;
			
	if(  dcheng(l1.a,l2.a,l2.b)<=0
	   ||dcheng(l1.b,l2.a,l2.b)<=0
	   ||dcheng(l2.a,l1.a,l1.b)<=0
	   ||dcheng(l2.b,l1.a,l1.b)<=0)return 2;
	return 0;
	
}
/////////////////////////////////////////////////////////////////
int in(point *p,int n,point judge)
{int c,j,k;point up,low,temp;	
	      c=0;
	      j=0;
	      while(p[j].y==judge.y)j++;
	      for(;j<n;j=k)
	      {	k=j+1;
	 	
		while(p[k%n].y==judge.y&&p[k%n].x>judge.x)k++;
				up=p[j];
   		low=p[k%n];
		if(up.y<low.y){temp=up;up=low;low=temp;}
		
		if(up.y<judge.y||low.y>judge.y)continue;
		if(cheng(low,up,judge)<=0&&k==j+1)continue;
		c++;
		}
		if(c%2)return 1;
		return 0;
}
/////////////////////////////
//对称点

point duicheng(point o,line l)
{double dx=l.b.x-l.a.x,
		dy=l.b.y-l.a.y,
		s1=-l.a.x*dy+l.a.y*dx,
		s2=-o.x*dx-o.y*dy;
point an;
an.y=-(s2*dy-s1*dx)/(dy*dy+dx*dx);
if(dy)an.x=dx*(an.y-l.a.y)/dy+l.a.x;
else an.x=o.x;

an.x=an.x*2-o.x;
an.y=an.y*2-o.y;
return an;
}

/////////////////////////////////////////

int duit()
{int i,j;
line l,l1;point c,p[4];
for(i=1;i<n;i++)
{l.a=a[i];l.b=b[i];
for(j=0;j<i;j++){a[j]=duicheng(a[j],l);b[j]=duicheng(b[j],l);}

if(d[i]!=d[i+1])continue;
l.a=a[i+1];l.b=b[i+1];

for(j=0;j<=i;j++)
{l1.a=a[j];l1.b=b[j];
if(jiao(l,l1)==1)break;}
if(j<=i){return i+1;}

for(j=0;j<i;j++){l1.a=a[j];l1.b=a[j+1];if(jiao(l,l1)==1)break;}
if(j<i){return i+1;}

for(j=0;j<i;j++){l1.a=b[j];l1.b=b[j+1];if(jiao(l,l1)==1)break;}
if(j<i){return i+1;}

c.x=(l.a.x+l.b.x)/2;
c.y=(l.a.y+l.b.y)/2;

for(j=1;j<=i;j++)
{p[0]=a[j-1];p[1]=b[j-1];p[2]=b[j];p[3]=a[j];
if(in(p,4,c))return i+1;
}

}
return 0;
}

int main()
{int s;
while(1)
{cin>>n;
if(!n)break;
init();
if((s=duit())==0)cout<<"YES"<<endl;
else cout<<"NO "<<s<<endl;
}
return 0;
}