POJ1039Pipe判断直线与线段相交（规范相交，非规范相交），没有共线情况

#include
#include<string.h>
#include
#include
using namespace std;
#define eps 10e-8
#define inf 1<<29
struct point
{
    double x, y;
};

double det(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - x2 * y1;
}
double cross(point o, point a, point b)
{
    return det(a.x - o.x, a.y - o.y, b.x - o.x, b.y - o.y);
}

bool seg_cross(point a, point b, point c, point d)//判断直线 和 线段是否相交（规范相交 ，非规范相交，不考虑共线）
{
    return ( cross(a, b, c) * cross(a, b, d) <= 0);
}

int dblcmp(double d)
{
    if( fabs(d) return 0;
    return d > 0 ? 1 : -1;
}
double intersection(point a, point b, point c, point d)//求直线 和线段的交点，
//注意 a，b是直线的端点，c，d是线段的端点，别调用错了
{
    double s1, s2;
    int d1, d2;
    d1 = dblcmp(s1 = cross(a, b, c));
    d2 = dblcmp(s2 = cross(a, b, d));
    if(d1 ^ d2 == -2) return (c.x * s2 - d.x * s1) / (s2 - s1);
    if(d1 == 0) return c.x;
    if(d2 == 0) return d.x;
    return - inf;
}

point up[22], down[22];
double tmp, max_x;

int main()
{
    int i, j, k, n;
    while( ~scanf("%d", &n) && n)
    {
        for(i = 1; i <= n; i++)
        {
            scanf("%lf%lf", &up[i].x, &up[i].y);
            down[i].y = up[i].y - 1;
            down[i].x = up[i].x;
        }
        max_x = up[1].x;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
            {
                if(i == j)continue;
                if( !seg_cross(up[i], down[j], up[1], down[1]) )//判断 枚举的直线与 入射口那垂直于x轴的线 是否相交， 相交说明能入射，否则不能，排除这情况
                    continue;
                for(k = 2; k <= n; k++)
                {
                    if( !seg_cross(up[i], down[j], up[k], down[k]))
                    {
                        if( seg_cross(up[i], down[j], up[k - 1], up[k]) )
                        {
                            tmp = intersection(up[i], down[j], up[k - 1], up[k]);
                            max_x = max (tmp, max_x);
                        }
                        if( seg_cross(up[i], down[j], down[k - 1], down[k]) )
                        {
                            tmp = intersection(up[i], down[j], down[k - 1], down[k]);
                            max_x = max (tmp, max_x);
                        }
                        break;
                    }
                }
                if(k == n + 1){ max_x = up[n].x; goto loop; }
            }
loop: if(max_x >= up[n].x)puts("Through all the pipe.");
      else printf("%.2f\n", max_x);
    }
    return 0;
}