思路:首先把问题转化为一个点(一个light),则变为从一个点射出的直线通过Pipe的问题.

#include <stdio.h>
#include <math.h>

struct coordinate
{
	double x,y;
};

double cross(coordinate p1,coordinate p2,coordinate p3)
{
	coordinate vector1,vector2;
	vector1.x=p2.x-p1.x;
	vector1.y=p2.y-p1.y;
	vector2.x=p3.x-p1.x;
	vector2.y=p3.y-p1.y;
	return vector1.x*vector2.y-vector1.y*vector2.x;
}

coordinate intersect(coordinate a1,coordinate a2,coordinate b1,coordinate b2)
{
	double s1=fabs(cross(a1,a2,b1)),s2=fabs(cross(a1,a2,b2)),s;
	coordinate point;
	s=s1+s2;
	point.x=(s1*b2.x+s2*b1.x)/s;
	point.y=(s1*b2.y+s2*b1.y)/s;
	return point;
}

int main()
{
	int i,n;
	coordinate light,temp;
	coordinate up0,down0;
	coordinate up,down,up_old,down_old,up_now,down_now;
	double max_x,temp1,temp2;

	scanf("%d",&n);
	while (n!=0)
	{
		scanf("%lf%lf",&up0.x,&up0.y);
		scanf("%lf%lf",&up.x,&up.y);
		down0.x=up0.x;down0.y=up0.y-1;
		down.x=up.x;down.y=up.y-1;
		up_old=up;down_old=down;
		light.x=(up0.x+up.x)/2;
		light.y=(up0.y+down.y)/2;
		for (i=2;i<n;i++)
		{
			scanf("%lf%lf",&up_now.x,&up_now.y);
			down_now.x=up_now.x;down_now.y=up_now.y-1;
			temp1=cross(light,down,down_now);
			if (temp1>=0)
			{
				temp2=cross(light,up,down_now);
				if (temp2<=0)
					down=down_now;
				else
				{
					temp=intersect(light,up,down_old,down_now);
					max_x=temp.x;
					break;
				}
			}

			temp1=cross(light,up,up_now);
			if (temp1<=0)
			{
				temp2=cross(light,down,up_now);
				if (temp2>=0)
					up=up_now;
				else
				{
					temp=intersect(light,down,up_old,up_now);
					max_x=temp.x;
					break;
				}
			}

			up_old=up_now;down_old=down_now;
		}

		if(i==n)
			printf("Through all the pipe.\n");
 		else
			printf("%.2lf\n",max_x);

		scanf("%d",&n);
	}
	return 0;
}

• Re:各位大虾帮忙看看为何WA,例程已经通过.(附思路) (4) hongxian 2007-05-23 09:57:20