题目地址：http://poj.org/problem?id=2826

题目：

给出两条线段（木板的侧切面，木板宽度默认为1），求能接住雨水的水量，保留两位小数

 

解题思路：

这道题有很多种情况需要考虑。

（1）首先判断两条线段是否相交且只有一个交点。

（2）若满足条件（1），取交点上面的点（这些点才有用），最好的情况是线段L1的a点在交点上方，线段L2的b点在交点上方，那么剩下的只需要求a、交点、b组成的形状最终能够接住多少水量。a、交点、b组成的形状又可细分为下面几种：

上述三类情况计算面积的方法都是相同的：设y=较低点.y   与 两条射线交点的横坐标的差值为X

s = 0.5 *（较低点.y-交点.y）* X，故可归于一大类。

 

注意上述两类情况有些情况是接不到水的，已在图中标明，要特判。这两类情况计算面积的方法是一样的：设y=较低点.y  与 两条射线交点分别为aa,bb：

s = 0.5 * sin(夹角) * Length(aa-c) * Length(bb-c)（计算方法不限这一种），故可归于一大类。

较低点要么是a，要么是b，判断一下即可，本题中，一些距离和差值的计算可以通过三角形形似得出公式，在判断和比较的过程中为了避免精度，要用dcmp。

wa到怀疑人生的点：最终结果+eps再输出?

 

ac代码：

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
const double eps = 1e-10;
const double pi = acos(-1.0);
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
    if (fabs(x) < eps)return 0; //等于
    else return x < 0 ? -1 : 1;//小于，大于
}
struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x),y(y){}
    bool operator ==(const Point& rhs) const {
        return dcmp(x-rhs.x)==0 && dcmp(y-rhs.y)==0;
    }
};
typedef Point Vector;
Vector operator - (Vector a, Vector b)//向量减法
{
    return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)//向量数乘
{
    return Vector(a.x * p, a.y * p);
}
Vector operator + (Vector a, Vector b)//向量加法
{
    return Vector(a.x + b.x, a.y + b.y);
}

double Dot(Vector a, Vector b)//点积
{
    return a.x * b.x + a.y * b.y;
}
double Length(Vector a)//模
{
    return sqrt(Dot(a, a));
}
double Cross(Vector a, Vector b)//外积
{
    return a.x * b.y - a.y * b.x;
}
double Angle(Vector a, Vector b)//夹角,弧度制
{
    return acos(Dot(a, b) / Length(a) / Length(b));
}
double Atan(Point a)//极角
{
    return atan2(a.y, a.x);
}

bool JudgeSegmentInter(Point A, Point B, Point C, Point D) //线段相交（包括端点）
{
    return
            dcmp(max(A.x, B.x) - min(C.x, D.x)) >= 0
            && dcmp(max(C.x, D.x) - min(A.x, B.x)) >= 0
            && dcmp(max(A.y, B.y) - min(C.y, D.y)) >= 0
            && dcmp(max(C.y, D.y) - min(A.y, B.y)) >= 0
            && dcmp(Cross(C - A, D - A)*Cross(C - B, D - B)) <= 0
            && dcmp(Cross(A - C, B - C)*Cross(A - D, B - D)) <= 0;
}

Point SegmentIntersection(Point a,Point b,Point c,Point d)
{
    Point s;
    double  a1=a.y-b.y,b1=b.x-a.x,c1=a.x*b.y-b.x*a.y;
    double  a2=c.y-d.y,b2=d.x-c.x,c2=c.x*d.y-d.x*c.y;
    s.x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
    s.y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
    return s;
}
double alow(Point a, Point b, double L2,  double y)
{
    return L2*(a.y-y)/(b.y-y);
}
double blow(Point a,Point b, double L1, double y)
{
    return  L1*(b.y-y)/(a.y-y);
}
double getL(Point a, Point b, double L1, double L2, double y)
{
    if(dcmp(a.y-b.y) <= 0)
        return alow(a, b, L2, y)*L1;
    else return blow(a, b, L1, y)*L2;
}

double solve(Point A1, Point B1, Point A2, Point B2)
{
    double ans = 0;
    vector<Point> a, b;
    if(JudgeSegmentInter(A1, B1, A2, B2) && dcmp(Cross(A1-B1, A2-B2))!=0) //保证线段有唯一交点
    {
        Point c = SegmentIntersection(A1, B1, A2, B2);
        //只保留交点上方的
        if(dcmp(A1.y-c.y) > 0) a.push_back(A1);
        if(dcmp(B1.y-c.y) > 0) a.push_back(B1);
        if(dcmp(A2.y-c.y) > 0) b.push_back(A2);
        if(dcmp(B2.y-c.y) > 0) b.push_back(B2);
        for(int i = 0; i < a.size(); i++)
        {
            for(int j = 0; j < b.size(); j++)
            {
                if(dcmp(dcmp(a[i].x-c.x) * dcmp(b[j].x-c.x)) <= 0)//两侧或中间
                {
                    if(dcmp(a[i].y - b[j].y) >= 0)//a在上
                    {
                        double x = fabs(a[i].x-c.x)*(b[j].y-c.y)/(a[i].y-c.y);
                        ans = 0.5 * (b[j].y-c.y) * (fabs(b[j].x-c.x)+x);
                    }
                    else//b在上
                    {
                        double x = fabs(b[j].x-c.x)*(a[i].y-c.y)/(b[j].y-c.y);
                        ans = 0.5 * (a[i].y-c.y) * (fabs(a[i].x-c.x)+x);
                    }
                }
                else//同侧
                {
                    double L1 = Length(a[i]-c), L2 = Length(b[j]-c);
                    double ang = Angle(a[i]-c, b[j]-c);
                    double L = getL(a[i], b[j], L1, L2, c.y);
                    double ka = Atan(a[i]-c), kb = Atan(b[j]-c);

                    if(dcmp(a[i].x-c.x) < 0 && dcmp(b[j].x-c.x) < 0)//同在左侧
                    {
                        if(dcmp(ka-kb) < 0 && dcmp(a[i].x-b[j].x) > 0)//a在上
                            ans = 0.5 * sin(ang) * L;
                        if(dcmp(kb-ka) < 0 && dcmp(b[j].x-a[i].x) > 0)//b在上
                            ans = 0.5 * sin(ang) *  L;
                    }
                    else //同在右侧
                    {
                        if(dcmp(ka-kb) > 0 && dcmp(a[i].x -b[j].x) < 0)//a在上
                            ans = 0.5 * sin(ang) * L;
                        if(dcmp(kb-ka) > 0 && dcmp(b[j].x-a[i].x) < 0)//b在上
                            ans = 0.5 * sin(ang) * L;
                    }

                }
            }
        }
        return ans;
    }
    else return 0;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t;
    Point A1, B1, A2, B2;
    scanf("%d",  &t);
    while(t--)
    {
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &A1.x, &A1.y, &B1.x, &B1.y, &A2.x, &A2.y, &B2.x, &B2.y);
        double ans = solve(A1, B1, A2, B2);
        printf("%.2lf\n", ans+eps);
    }
    return 0;
}