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

typedef struct {
	double x, y;
}point;
int dblcmp (double d)    //判断d的符号
{
	if (fabs (d) < 1e-6) return 0;
	return (d > 0) ? 1 : -1;
}
void getline (point a, point b, double &k, double &t, double &c)  
{   //根据点a，b求直线kx+ty+c=0 
	k = a.y - b.y;
	t = b.x - a.x;
	c = a.x*b.y - b.x*a.y;
	return ;
}
int cal (double k, double t, double c, point a) 
{//计算点a在直线kx+ty+c=0的上方还是下方还是直线上
	return dblcmp (k*a.x + t*a.y + c);
}
int n;
const int size = 21;
point up[size], down[size];
double max;
void updata (double k, double t, double c, point a, point b)
{ //更新最大值
	double k2, t2, c2;
	getline (a, b, k2, t2, c2);
	double xp = (t*c2 - t2*c) / (k*t2 - t*k2);
	double dist;
	dist = (xp - up[0].x) * sqrt ((k*k)/(t*t) + 1);
	if (dist > max) max = dist;	
	return ;
}
bool judge (point a, point b)
{  // 判断点a，b构成的直线是否能通过整条管道
	double k, t, c;
	getline (a, b, k, t, c);
	//判断光线能够从第一个通道口射入
	if (cal(k, t, c, up[0]) * cal(k, t, c, down[0]) > 0) return false;
	int i;
	//寻找第一个拐角，在这个拐角前，光线已穿越管壁
	for (i = 1; i < n; i++) 
		if (cal(k, t, c, up[i]) * cal(k, t, c, down[i]) > 0) break; 
	if (i == n) return true;
	if (cal(k, t, c, up[i]) * cal(k, t, c, up[i-1]) <= 0) updata (k, t, c, up[i], up[i-1]);
	if (cal(k, t, c, down[i]) * cal(k, t, c, down[i-1]) <= 0) updata (k, t, c, down[i], down[i-1]);
	return false;
}
bool solve ()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++){
			if (i == j) continue;
			if (judge (up[i], down[j])) return true;
		}
	return false;
}

int main ()
{
//	freopen ("in.txt", "r", stdin);
	while (scanf ("%d", &n), n){
		for (int i = 0; i < n; i++){
			scanf ("%lf%lf", &up[i].x, &up[i].y);
			down[i].x = up[i].x; down[i].y = up[i].y - 1;
		}
		max = 0;
		if (solve ()) printf ("Through all the pipe.\n");
		else printf ("%.2f\n", max);
	}
}

• Re:打死我也不做计算几何题. (0) MasterLuo 2008-07-10 14:19:31
  • Re:打死我也不做计算几何题. (8) bloodmary 2008-07-10 14:24:04
    • Re:唯一成功写过一次TU包. (12) MasterLuo 2008-07-10 15:00:25
• 题意看错了，疯掉。。。。 原来求的是最远的X，我求成了距离。。。。 (2021) bloodmary 2008-07-10 19:24:22