An Easy Problem?(poj2826线段相交,直线线段相交)

An Easy Problem?!(poj2826线段相交,直线线段相交)

题意：给你两个同样长的木板，围城一个多边形，水从空中垂直下落，问木板能盛放多少体积的水。

思路：分类讨论

1.如果线段没有交点，那么面积就是0

2.如果线段有交点，但是有一个模板被另一个木板覆盖还是接不到水，怎么判断了，过两个木板的最高的两个点做垂线，如果垂线和和交点到另一木板的顶点这段相交，说明木板有覆盖，不行可以画个图试试，但是覆盖不一定遮挡，所以要判断交点是在另一个木板顶点的上下，在上面说明木板被覆盖，面积为0，反之没有

3.因为盛水是水平的，所以过另个木板的顶点做水平线，如果水平线的交点在交点和顶点之间，那么面积就是这三个顶点的面积

这题需要直线与线段相交，线段与线段相交，点在线段和点在直线上。

直线与线段相交，只要有一个叉乘小于0即可，但是有可能叉乘等于0，一个点在直线上，还要判断点是否在线段上，用点到直线的距离，距离为0就在，反之就不再

点到直线距离，面积除以底。

直线与线段的交点，求出直线与直线的交点，判断他是否在线段上，判线段上还要注意端点，

线段与线段的交点，也是求出直线与直线的交点 ，判断他是否同时在两个线段上，或者可以先判断两个线段是否相交，然后直接求交点

点在线段上，叉积和点积同时用并且在判断是否在两端点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point
{
    double x,y;
    Point(double x = 0,double y = 0):x(x),y(y){}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b) { return Vector(a.x+b.x,a.y+b.y) ;}
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,double p) { return Vector(a.x/p,a.y/p) ;}
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 ;}
const double eps = 1e-8;
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
bool operator == (Point a,Point b)
{
    return dcmp(a.x-b.x) == 0&& dcmp(a.y-b.y) == 0;
}
bool operator < (Point a,Point b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}


bool Onsegment(Point p,Point a,Point b)
{
    return dcmp(Cross(b-a,p-a)) == 0 && dcmp(Dot(b-p,a-p)) < 0 || (p == a) || (p == b);
}

bool OnLine(Point p,Point a,Point b)
{
    return fabs(Cross(p-a,a-b)) / Length(b-a);
}

bool SegmentIntersection(Point a,Point b,Point c,Point d)
{
    double d1 = Cross(b-a,c-a),d2 = Cross(b-a,d-a),d3 = Cross(d-c,a-c),d4 = Cross(d-c,b-c);
    if(dcmp(d1)*dcmp(d2) < 0 || dcmp(d3)*dcmp(d4) < 0) return true;
    else if(dcmp(d1) == 0 && !OnLine(c,a,b) ) return true;
    else if(dcmp(d2) == 0 && !OnLine(d,a,b) ) return true;
    else if(dcmp(d3) == 0 && !OnLine(a,c,d) ) return true;
    else if(dcmp(d4) == 0 && !OnLine(b,c,d) ) return true;
    else return false;
}

bool Segmentsection(Point a,Point b,Point c,Point d)
{
    double d1 = Cross(b-a,c-a),d2 = Cross(b-a,d-a),d3 = Cross(d-c,a-c),d4 = Cross(d-c,b-c);
    if(dcmp(d1)*dcmp(d2) < 0 && dcmp(d3)*dcmp(d4) < 0) return true;
    else if(dcmp(d1) == 0 && Onsegment(c,a,b) ) return true;
    else if(dcmp(d2) == 0 && Onsegment(d,a,b) ) return true;
    else if(dcmp(d3) == 0 && Onsegment(a,c,d) ) return true;
    else if(dcmp(d4) == 0 && Onsegment(b,c,d) ) return true;
    else return false;
}
bool pointInpoly(Point p,Point a,Point b,Point c,Point d)
{
    double d1 = Cross(b-a,p-a);
    double d2 = Cross(d-c,p-c);
    double d3 = Cross(c-b,p-b);
    double d4 = Cross(a-d,p-d);
    return dcmp(d1)*dcmp(d2) > 0 && dcmp(d3)*dcmp(d4) > 0;
}

Point Segment(Point p,Vector v,Point q,Vector w)
{
    Vector u = p-q;
    double t = Cross(w,u) / Cross(v,w);
    return p + v*t;
}
struct Line
{
    Point s,e;
    Line(Point s = 0,Point e = 0) :s(s),e(e){}
};


Point Max(Point a,Point b)
{
    return a.y > b.y ? a : b;
}


int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        Point a,b,c,d;
        scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
        Point P1 = Max(a,b);
        Point P2 = Max(c,d);
        if(!Segmentsection(a,b,c,d)) printf("0.00\n");
        else if(a.y == b.y || c.y == d.y) printf("0.00\n");
        else if(!Cross(b-a,c-d)) printf("0.00\n");
        else
        {
            Point k = Segment(a,b-a,c,d-c);
            Point P3 = Point(P1.x,P1.y+1);
            Point P4 = Point(P2.x,P2.y+1);

            if(SegmentIntersection(P1,P3,c,d))
            {
                Point k1 = Segment(P1,P3-P1,c,d-c);
                if(Onsegment(k1,P2,k))
                {
                    if(dcmp(P1.y-k1.y) <= 0)
                    {
                        printf("0.00\n");continue;
                    }
                }
            }
            if(SegmentIntersection(P2,P4,a,b))
            {
                Point k1 = Segment(P2,P4-P2,a,b-a);
                if(Onsegment(k1,P1,k))
                {
                    if(dcmp(P2.y-k1.y) <= 0)
                    {
                         printf("0.00\n");continue;
                    }
                }
            }

            P3 = Point(P1.x+1,P1.y);
            P4 = Point(P2.x+1,P2.y);
            if(SegmentIntersection(P1,P3,c,d))
            {
                Point k1 = Segment(P1,P3-P1,c,d-c);
                if(Onsegment(k1,P2,k))
                    printf("%.2lf\n",fabs(Cross(P1-k,k1-k))/2);continue;
            }
            if(SegmentIntersection(P2,P4,a,b))
            {
                Point k1 = Segment(P2,P4-P2,a,b-a);
                if(Onsegment(k1,P1,k))
                    printf("%.2lf\n",fabs(Cross(P2-k,k1-k))/2);continue;
            }
        }
    }
    return 0;
}