1039.txt

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

#include"iostream.h"
#include"stdio.h"
#include"math.h"
#include<vector>
#include<algorithm>
using namespace std;

/////////////////////////
#define Type double /*坐标类型*/
/////////////////////////


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

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),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);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.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;
}

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

point p1[21], p2[21], pt;

int main()
{
	int i, j, k, n;
	double a, b, ans;
	line l;
	
	while( 1 )
	{
		scanf( "%d", &n );
		if( n == 0 ) break;
		
		for( i=0; i<n; i++ )
		{
			scanf( "%lf %lf", &p1[i].x, &p1[i].y );
			p2[i].x = p1[i].x;
			p2[i].y = p1[i].y-1;
		}

		ans = p1[0].x;

		for( i=0; i<n; i++ )
		for( j=0; j<n; j++ )
		if( i != j )
		{
			l.a = p1[i], l.b = p2[j];

			if( l.a.x > l.b.x )
				swap( l.a, l.b );
			
			for( k=0; k<n; k++ )
				if( cheng( l.a, l.b, p1[k] ) < -1e-7 )
					break;

			if( k == 0 )
				continue;
			
			if( k < n )
				a = ( pt = crosspoint( l, line( p1[k], p1[k-1] ) ) ).x;
			else a = p1[n-1].x;

			for( k=0; k<n; k++ )
			if( cheng( l.a, l.b, p2[k] ) > 1e-7 )
				break;

			if( k == 0 )
				continue;
				
			if( k < n )
				b = crosspoint( l, line( p2[k], p2[k-1] ) ).x;
			else b = p1[n-1].x;

			if( a > b ) a = b;
			if( a > ans )
				ans = a;

		}

		if( ans == p1[n-1].x )
			printf( "Through all the pipe.\n" );
		else printf( "%.2lf\n", ans );
	}

	return 0;
}