学步园

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. 

The first line contains the number of test cases. 
Each test case consists of 8 integers not exceeding 10,000 by absolute value, x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄.
(x₁, y₁), (x₂, y₂) are the endpoints of one board, and (x₃, y₃), (x₄, y₄) are the endpoints of the
other one. 

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

2
0 1 1 0
1 0 2 1

0 1 2 1
1 0 1 2

1.00
0.00

POJ Monthly--2006.04.28, Dagger@PKU_RPWT

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

题意：求两条线段围成的图形能容纳的面积

分析：这题题目描述，还有第一眼看，都很简单，但是去无数的wa。。。就算该想到的情况都想到了，最后还要在答案上加个精度，尽管这可能是我算法比较挫- -

注意点：

1.两线段是否相交

2.两线段是否共线，是否水平

3.接水口是否被覆盖

这几点都考虑过了，就试试精度问题吧 T_T

这题真是不简单啊、、、

代码：

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
typedef double mType;
struct Tpoint
{
    mType x,y;
    Tpoint(){}
    Tpoint(mType _x,mType _y):x(_x),y(_y){}
};
struct Tsegment
{
    Tpoint s,t;
    Tsegment(){}
    Tsegment(Tpoint _s,Tpoint _t):s(_s),t(_t){}
    Tsegment(mType sx,mType sy,mType tx,mType ty):s(sx,sy),t(tx,ty){}
};
struct Tline
{
    mType A,B,C;
    Tline(){}
    Tline(Tpoint P,Tpoint Q)
    {
        A=P.y-Q.y;
        B=Q.x-P.x;
        C=P.x*Q.y-P.y*Q.x;
    }
    Tpoint IntersectPoint(Tline P)
    {
        mType tmp=P.B*A-P.A*B;
        return Tpoint((P.C*B-P.B*C)/tmp,(P.A*C-P.C*A)/tmp);
    }
    int IsIntersect(Tline P)
    {
        if(fabs(A*P.B-B*P.A)<1e-8)
        {
            /**这里注意AC和BC都要判断,不然会WA*/
            if(fabs(A*P.C-C*P.A)<1e-8&&fabs(B*P.C-C*P.B)<1e-8)return -1;
            return 0;
        }
        return 1;
    }
};
Tpoint MakeVector(Tpoint P,Tpoint Q)
{
    return Tpoint(Q.x-P.x,Q.y-P.y);
}
mType CrossProduct(Tpoint P,Tpoint Q)
{
    return P.x*Q.y-P.y*Q.x;
}
mType MultiCross(Tpoint P,Tpoint Q,Tpoint R)
{
    return CrossProduct(MakeVector(Q,P),MakeVector(Q,R));
}
bool IsIntersect(Tsegment P,Tsegment Q)
{
    if(max(P.s.x,P.t.x)<min(Q.s.x,Q.t.x)||max(P.s.y,P.t.y)<min(Q.s.y,Q.t.y)||
       max(Q.s.x,Q.t.x)<min(P.s.x,P.t.x)||max(Q.s.y,Q.t.y)<min(P.s.y,P.t.y))return 0;
    return (MultiCross(P.t,P.s,Q.s)*MultiCross(P.t,P.s,Q.t)<=0&&
            MultiCross(Q.t,Q.s,P.s)*MultiCross(Q.t,Q.s,P.t)<=0);
}
mType GetDis(Tpoint P,Tpoint Q)
{
    return sqrt((P.x-Q.x)*(P.x-Q.x)+(P.y-Q.y)*(P.y-Q.y));
}
mType area(Tpoint A,Tpoint B,Tpoint C)
{
    mType l1,l2,l3,p;
    l1=GetDis(A,B);
    l2=GetDis(A,C);
    l3=GetDis(B,C);
    p=(l1+l2+l3)/2.0;
    return sqrt(p*(p-l1)*(p-l2)*(p-l3));
}
void test()
{
    Tline P=Tline(Tpoint(0,0),Tpoint(1,1));
    Tline Q=Tline(Tpoint(0,1),Tpoint(1,0));
    printf("P: %lf %lf %lf\n",P.A,P.B,P.C);
    printf("Q: %lf %lf %lf\n",Q.A,Q.B,Q.C);
    Tpoint tmp=P.IntersectPoint(Q);
    printf("The intersect point: %lf %lf\n",tmp.x,tmp.y);
}
mType sx,sy,tx,ty,my;
Tline L1,L2,L3;
Tpoint A,B,C;
Tsegment P,Q;
bool ok()
{
    if(P.s.y==P.t.y||Q.s.y==Q.t.y||IsIntersect(P,Q)==0)return 0;
    L1=Tline(P.s,P.t);
    L2=Tline(Q.s,Q.t);
    A=L1.IntersectPoint(L2);
    Tpoint tmp1,tmp2;
    tmp1=P.s.y>P.t.y?P.s:P.t;
    tmp2=Q.s.y>Q.t.y?Q.s:Q.t;
    if(tmp1.y>tmp2.y)
    {
        B=tmp2;
        C=Tpoint(-(tmp2.y*L1.B+L1.C)/L1.A,tmp2.y);
        if((B.x-C.x)*(tmp1.x-C.x)>=0&&fabs(tmp1.x-C.x)-fabs(B.x-C.x)>-1e-8)return 0;
    }
    else
    {
        B=tmp1;
        C=Tpoint(-(tmp1.y*L2.B+L2.C)/L2.A,tmp1.y);
        if((B.x-C.x)*(tmp2.x-C.x)>=0&&fabs(tmp2.x-C.x)-fabs(B.x-C.x)>-1e-8)return 0;
    }
    return 1;
}
int main()
{
   // test();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lf%lf%lf%lf",&sx,&sy,&tx,&ty);
        P=Tsegment(sx,sy,tx,ty);
        scanf("%lf%lf%lf%lf",&sx,&sy,&tx,&ty);
        Q=Tsegment(sx,sy,tx,ty);
        if(ok())printf("%.2lf\n",area(A,B,C));
        else puts("0.00");
    }
    return 0;
}