POJ 2826 An Easy Problem?!(计算几何)

Description:

It’s raining outside. Farmer Johnson’s bull Ben wants some rain to water his flowers. Ben nails two wooden boards on the wall of his barn. Shown in the pictures below, the two boards on the wall just look like two segments on the plane, as they have the same width.

Your mission is to calculate how much rain these two boards can collect.

Input:

The first line contains the number of test cases.
Each test case consists of 8 integers not exceeding 10,000 by absolute value, x1, y1, x2, y2, x3, y3, x4, y4. (x1, y1), (x2, y2) are the endpoints of one board, and (x3, y3), (x4, y4) are the endpoints of the other one.

Output:

For each test case output a single line containing a real number with precision up to two decimal places - the amount of rain collected.

Sample Input:

2
0 1 1 0
1 0 2 1

0 1 2 1
1 0 1 2

Sample Output:

1.00
0.00

题目链接

给出两条线段，求两条线段能接到多少从竖直上方落下的雨水（求面积）。

两条线段的位置可以分为几种情况：

1. 两条线段不相交
2. 至少一条线段与x轴平行
3. 线段相交但交点上方线段两端点其y值较小点被另一线段遮挡
4. 线段相交

其中前三种情况是接不到雨水的。

PS:此题要交C++，G++我一直WA。

AC代码:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
    double X, Y;

    Point() {}
    Point(double _X, double _Y) {
        X = _X;
        Y = _Y;
    }

    void Input() {
        scanf("%lf%lf", &X, &Y);
    }

    Point operator - (const Point &B) const {
        return Point(X - B.X, Y - B.Y);
    }

    double operator * (const Point &B) const {
        return X * B.X + Y * B.Y;
    }

    double operator ^ (const Point &B) const {
        return X * B.Y - Y * B.X;
    }
};

struct Segment {
    Point S, T;

    Segment() {}
    Segment(Point _S, Point _T) {
        S = _S;
        T = _T;
    }

    void Input() {
        S.Input();
        T.Input();
    }

    double operator ^ (const Segment &B) const {
        return (T - S) ^ (B.T - B.S);
    }
};

bool IsIntersect(Segment A, Segment B){
    return 
        max(A.S.X, A.T.X) >= min(B.S.X, B.T.X) &&
        max(B.S.X, B.T.X) >= min(A.S.X, A.T.X) &&
        max(A.S.Y, A.T.Y) >= min(B.S.Y, B.T.Y) &&
        max(B.S.Y, B.T.Y) >= min(A.S.Y, A.T.Y) &&
        (A ^ Segment(A.S, B.S)) * (A ^ Segment(A.S, B.T)) < eps &&
        (B ^ Segment(B.S, A.S)) * (B ^ Segment(B.S, A.T)) < eps;
}

Point IntersectionPoint(Segment A, Segment B) {
    double X = (B.T - B.S) ^ (A.S - B.S), Y = (B.T - B.S) ^ (A.T - B.S);
    return Point((A.S.X * Y - A.T.X * X) / (Y - X), (A.S.Y * Y - A.T.Y * X) / (Y - X));
}

// POJ 2826 此题要交C++,G++会Wrong Answer

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        Segment O, P;
        O.Input();
        P.Input();
        if (O.S.Y == O.T.Y || P.S.Y == P.T.Y) {
            printf("0.00\n");
        }
        else if (IsIntersect(O, P)) {
            Point CrossPoint = IntersectionPoint(O, P);
            Point TopPoint[2];
            int Flag = 0;
            if (O.S.Y > CrossPoint.Y) {
                TopPoint[Flag++] = O.S;
            }
            if (O.T.Y > CrossPoint.Y) {
                TopPoint[Flag++] = O.T;
            }
            if (P.S.Y > CrossPoint.Y) {
                TopPoint[Flag++] = P.S;
            }
            if (P.T.Y > CrossPoint.Y) {
                TopPoint[Flag++] = P.T;
            }
            if (Flag < 2) {
                printf("0.00\n");
                continue;
            }
            if (TopPoint[1].Y < TopPoint[0].Y) {
                swap(TopPoint[0], TopPoint[1]);
            }
            if (IsIntersect(Segment(CrossPoint, TopPoint[1]), Segment(TopPoint[0], Point(TopPoint[0].X, TopPoint[0].Y + 10005)))) {
                printf("0.00\n");
                continue;
            }
            TopPoint[1] = IntersectionPoint(Segment(CrossPoint, TopPoint[1]), Segment(Point(TopPoint[0].X - 2, TopPoint[0].Y), TopPoint[0]));
            double Ans = fabs(((TopPoint[1] - CrossPoint) ^ (TopPoint[0] - CrossPoint))) / 2;
            printf("%.2lf\n", Ans + eps);
        }
        else {
            printf("0.00\n");
        }
    }
	return 0;
}