POJ 3304 Segments

大意：给你一些线段，找出一条直线可以穿过全部的线段，相交包含端点。

思路：遍历全部的端点，取两个点形成直线，推断直线是否与全部线段相交，假设存在这种直线，输出Yes。可是注意去重。

struct Point

{

    double x, y;

} P[210];

struct Line

{

    Point a, b;

} L[110];

double xmult(Point p1, Point p2, Point p)

{

    return (p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x);

}

bool segLineInter(Line seg, Line line)

{

    double d1, d2;

    d1 = xmult(seg.a, line.a, line.b);

    d2 = xmult(seg.b, line.a, line.b);

    if((d1>eps && d2 < -eps) || (d1 < -eps && d2 > eps))

        return true;

    if(fabs(d1) < eps || fabs(d2) < eps)

        return true;

    return false;

}

int T;

int n;

void Solve()

{

    Line l1, l2;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        int t = 0;

        for(int i = 0; i < n; ++i)

        {

            scanf("%lf%lf%lf%lf", &L[i].a.x, &L[i].a.y, &L[i].b.x, &L[i].b.y);

            P[t++] = L[i].a;

            P[t++] = L[i].b;

        }

        bool ans = false;

        for(int i = 0; !ans && i < t; ++i)

        {

            for(int j = i+1; j < t; ++j)

            {

                bool flag = true;

                if(fabs(P[i].x-P[j].x) < eps && fabs(P[i].y-P[j].y) < eps) continue;

                for(int k = 0; k < n; ++k)

                {

                    if(segLineInter(L[k], (Line){P[i], P[j]}) == false)

                    {

                        flag = false;

                        break;

                    }

                }

                if(flag == true)

                {

                    ans = true;

                    break;

                }

            }

        }

        printf("%s!\n", ans?"Yes":"No");

    }

}