# POJ PKU 2826 An Easy Problem?! 解题报告

题目链接： <http://acm.pku.edu.cn/JudgeOnline/problem?id=2826>

大致意思是给你两条线段，问组成的开口向上的V形区域能盛多少雨水。雨水是垂直落下的。

显然线段不相交，或者平行，重合，或者有一条斜率为0时结果为0.00

然后还有一种情况结果为0的，就是高的那条线段被低的挡住了。

判断覆盖可以从最高点较低的线段的最高点引一条向y轴正向的线段，线段最高点坐标大于10000（题目说的坐标绝对值不大于10000），然后判断线段是否和原来两条线段都相交，是则输出0.00

最后还要注意精度，我是结果加上eps才过的，面积计算使用的是海伦公式。

提供几组数据

Input：

```
0 0 100 100
0 0 100 99

0 0 100 100
0 0 101 99

0 0 1 1
0 0 2 2

0 0 -100 100
0 0 100 99

0 0 1 1
1 1 2 2
```

Output:

```
0.00

99.00

0.00

9850.50

0.00
```

代码如下：

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>

const double eps = 1e-8;
struct point
{
    int x, y;

    point(){}
    point(int _x, int _y):x(_x),y(_y){};

    static int xmult(const point &p1, const point &p2, const point & p0)
    {
        return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    }
    bool operator > (const point &_p) const
    {
        return y > _p.y;
    }
};

struct segment
{
    point s, e;

    segment(){}
    segment(const point &_s, const point &_e):s(_s),e(_e){}

    double operator *(const segment &_Off) const
    {
        return (e.x - s.x) * (_Off.e.y - _Off.s.y) - (e.y - s.y) * (_Off.e.x - _Off.s.x);
    }
    bool cross(const segment &_Off) const
    {
        return (
            (std::max(s.x, e.x) >= std::min(_Off.s.x, _Off.e.x)) &&
            (std::max(_Off.s.x, _Off.e.x) >= std::min(s.x, e.x)) &&
            (std::max(s.y, e.y) >= std::min(_Off.s.y, _Off.e.y)) &&
            (std::max(_Off.s.y, _Off.e.y) >= std::min(s.y, e.y)) &&
            ((segment(_Off.s, s) * _Off) * (_Off * segment(_Off.s, e)) >= 0.0) &&
            ((segment(s, _Off.s) * (*this)) * ((*this) * segment(s, _Off.e)) >= 0.0)
            );
    }

    bool par(const segment &_s) const
    {
        return (e.y - s.y) * (_s.e.x - _s.s.x) - (e.x - s.x) * (_s.e.y - _s.s.y) == 0;
    }

    bool her()
    {
        return s.y == e.y;
    }
};

std::pair<double, double> cross(const segment &a, const segment &b)
{
    double a1 = a.s.y - a.e.y;
    double b1 = a.e.x - a.s.x;
    double c1 = a.s.x * a.e.y - a.e.x * a.s.y;
    double a2 = b.s.y - b.e.y;
    double b2 = b.e.x - b.s.x;
    double c2 = b.s.x * b.e.y - b.e.x * b.s.y;
    return std::make_pair((c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2)
            , (c1 * a2 - c2 * a1) / (b2 * a1 - b1 * a2));
}

double dis(std::pair<double, double> a, std::pair<double, double> b)
{
    return std::sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double area(double a, double b, double c)
{
    double s = (a + b + c) / 2;
    return std::sqrt(s * (s - a) * (s - b) * (s - c));
}
std::pair<double, double> getpt(std::pair<double, double> x, const point &pt, double y)
{
    double py = pt.y - x.second;
    double px = pt.x - x.first;
    if(std::fabs(py) < eps)
        return x;
    return std::make_pair(x.first + (y - x.second) * px / py, y);
}

int main()
{
    segment a, b;
    point ap, bp, mxp, mnp;
    int i, t;
    std::scanf("%d", &t);
    while(t --)
    {
        std::scanf("%d %d %d %d %d %d %d %d"
            , &a.s.x, &a.s.y, &a.e.x, &a.e.y
            , &b.s.x, &b.s.y, &b.e.x, &b.e.y);
        if(a.her() || b.her() || a.cross(b) == false || a.par(b))
        {
            std::printf("0.00\n");
            continue;
        }
        ap = (a.s > a.e)? a.s: a.e;
        bp = (b.s > b.e)? b.s: b.e;

        std::pair<double, double> pt1, pt2, pt0 = ::cross(a, b);

        if((ap.x - pt0.first) * (bp.x - pt0.first) > eps)
        {
            mnp = (ap > bp)?bp: ap;
            if(segment(mnp, point(mnp.x, 30000)).cross(a) && segment(mnp, point(mnp.x, 30000)).cross(b))
            {
                std::printf("0.00\n");
                continue;
            }
        }

        if(ap > bp)
        {
            pt1 = std::make_pair(bp.x, bp.y);
            pt2 = ::getpt(pt0, ap, pt1.second);
        }
        else
        {
            pt1 = std::make_pair(ap.x, ap.y);
            pt2 = ::getpt(pt0, bp, pt1.second);
        }

        std::printf("%.2lf\n", ::area(::dis(pt0, pt1), ::dis(pt0, pt2), ::dis(pt2, pt1)) + eps);
    }
    return 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.owent.net/2010/19.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.