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

using namespace std;

typedef struct TPoint
{
    double x;
    double y;
}TPoint;

typedef struct TLine
{
    double a, b, c;
}TLine;

double maxx;
int maxp;
const double eps = 1e-6;
const double INF = 1e30;

TLine lineFromSegment(TPoint p1, TPoint p2)
{
    //线段所在直线,返回直线方程的三个系数 
    TLine tmp;
    tmp.a = p2.y - p1.y;
    tmp.b = p1.x - p2.x;
    tmp.c = p2.x * p1.y - p1.x * p2.y;
    return tmp;
}

TPoint LineInter(TLine l1, TLine l2)
{
    //求两直线得交点坐标
    TPoint tmp; 
    double a1 = l1.a;
    double b1 = l1.b;
    double c1 = l1.c;
    double a2 = l2.a;
    double b2 = l2.b;
    double c2 = l2.c;
    //注意这里b1 = 0 
    if(fabs(b1) < eps){
        tmp.x = -c1 / a1;  
        tmp.y = (-c2 - a2 * tmp.x) / b2;
    }       
    else{
        tmp.x = (c1 * b2 - b1 * c2) / (b1 * a2 - b2 * a1);
        tmp.y = (-c1 - a1 * tmp.x) / b1;
    }
    //cout << "交点坐标" << endl; 
    //cout << a1 * tmp.x + b1 * tmp.y + c1 << endl;
    //cout << a2 * tmp.x + b2 * tmp.y + c2 << endl;
	return tmp;
}

double multi(TPoint p1, TPoint p2, TPoint p0)
{
    //求矢量[p0, p1], [p0, p2]的叉积
    //p0是顶点 
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    //若结果等于0，则这三点共线
    //若结果大于0，则p0p2在p0p1的逆时针方向
    //若结果小于0，则p0p2在p0p1的顺时针方向 
}

bool isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2)
{
    //判断线段是否相交
    //1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交 
    //2.跨立试验
    if(
    (max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
    (max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
    (max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
    (max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
    (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
    (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
    )  return true;
    
    return false;    
}

bool Judge(int p, int q, int n, TPoint point[])
{
    int i, j, flag;
    double tmpy;
    bool TrueOrFalse;
    TLine linetmp;
    TPoint point2, interpoint; 
    TPoint tmp1, tmp2, tmp3, tmp4;   
    point2.x = point[q].x;
    point2.y = point[q].y - 1; 
    TLine line = lineFromSegment(point[p], point2);
    if(fabs(line.b) < eps) return false;      
    tmpy = (-line.c - line.a * point[0].x) / line.b;
    if(tmpy < point[0].y - 1 || tmpy > point[0].y) return false;
    flag = 0;
    for(i = 1;i < n;i++){
        tmpy = (-line.c - line.a * point[i].x) / line.b;
         if(tmpy < point[i].y - 1 || tmpy > point[i].y){
                if(i < maxp) return false; 
                else{ 
                    tmp3.x = -INF;
                    tmp3.y = (-line.c - line.a * tmp3.x) / line.b;
                    tmp4.x = INF;
                    tmp4.y = (-line.c - line.a * tmp4.x) / line.b;  
                    TrueOrFalse = isIntersected(tmp3, tmp4, point[i - 1], point[i]);
                    if(TrueOrFalse == true){
                        linetmp = lineFromSegment(point[i - 1], point[i]);
                        interpoint = LineInter(line, linetmp);
                        if(interpoint.x > maxx){
                             maxx = interpoint.x;
                             maxp = i;
                        }
                        flag = 1;
                    }
                    tmp1 = point[i - 1];
                    tmp2 = point[i];
                    tmp1.y -= 1.0;
                    tmp2.y -= 1.0;
                    TrueOrFalse = isIntersected(tmp3, tmp4, tmp1, tmp2);
                    if(TrueOrFalse == true){
                        linetmp = lineFromSegment(tmp1, tmp2);
                        interpoint = LineInter(line, linetmp);
                        if(interpoint.x > maxx){
                             maxx = interpoint.x;
                             maxp = i;
                           }
                        flag = 1;
                    }     
                }
        }
        if(flag == 1) break;
    }
    if(i == n) return true;
    else return false;
}


int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.out", "w", stdout);
    int n, i, j, tag;
    TPoint point[30];
    while(scanf("%d", &n) && n){
        for(i = 0;i < n;i++){
            scanf("%lf%lf", &point[i].x, &point[i].y);
        }
        maxp = -1;
        maxx = -INF;
        tag = 0;
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){
                if(i == j) continue;
                if(Judge(i, j, n, point)){
                    tag = 1;
                    break;
                }
            }
        } 
        if(fabs(maxx - point[n - 1].x) < eps) tag = 1;
        
        if(tag == 1) printf("Through all the pipe.\n");
        else printf("%.2lf\n", maxx); 
    }
    return 0;
}

• Re:我哪里错了，帮忙看看，谢谢了！ (21) chenhaifeng 2007-09-08 10:33:42
  • Re:可能是太有深度了，别人都不懂。 (25) 0nlylovePPmm 2007-09-08 11:19:24