[UVA] 191 - Intersection

題意:
給一條線段和一個四方形，
判斷線段是否與四方形有香蕉。

--------------------------------------------------

方法:
注意喔!四方形他是給你對角兩點，但不一定是左上右下，要自己判斷!

線段有起始點和終點，
有兩點就可以求出線段斜率，斜率 = (y1-y0)/(x1-x0) = (終點y-起點y)/(終點x-起點x)
垂直線要另外判斷，斜率用很大的數字表示。

先判斷該線段是否可能相交四方形，
線段的兩點x要與四邊形的左右x交疊，
兩點y要與四邊形的上下交疊，

再來判斷線段有沒有交四邊形，
假設線段斜率是m，
斜率為m的線段有無限條，
但是通過起點終點的只有一條，而直線方程式有一常數(位移量)，y=mx+a的a就是常數
現在將四邊形的四個頂點帶進去斜率為m的線段都會各自得到1個常數，
若四個常數有>=a也有<=a則表示四個點分布在線段兩邊，也就是線段跟四邊形有相交。


--------------------------------------------------

/* 20150922
 * hanting
 * UVa 191 - Intersection
 * C++
 */
#include <iostream>
using namespace std;
struct point
{
    double x,y;
    point(double _x=0,double _y=0):x(_x),y(_y){}
    friend istream& operator>>(istream& in,point &p)
    {
        in>>p.x>>p.y;
        return in;
    }
};
struct rectangle
{
    point topLeft,bottomRight;
    point topRight,bottomLeft;
    point v1,v2;
    friend istream& operator>>(istream& in,rectangle &r)
    {
        in>>r.v1>>r.v2;
        r.Build();
        return in;
    }
    void Build()//建立四邊形四個頂點
    {
        if(v1.x>v2.x)
        {
            if(v1.y>v2.y)
            {
                topRight=v1;
                bottomLeft=v2;

                topLeft=point(bottomLeft.x,topRight.y);
                bottomRight=point(topRight.x,bottomLeft.y);
            }
            else
            {
                bottomRight=v1;
                topLeft=v2;

                bottomLeft=point(topLeft.x,bottomRight.y);
                topRight=point(bottomRight.x,topLeft.y);
            }
        }
        else
        {
            if(v1.y>v2.y)
            {
                topLeft=v1;
                bottomRight=v2;

                topRight=point(bottomRight.x,topLeft.y);
                bottomLeft=point(topLeft.x,bottomRight.y);
            }
            else
            {
                bottomLeft=v1;
                topRight=v2;

                bottomRight=point(topRight.x,bottomLeft.y);
                topLeft=point(bottomLeft.x,topRight.y);
            }
        }
    }
    inline bool xCover(point &start,point &End)
    {
        return !(start.x>topRight.x and End.x>topRight.x) and !(start.x<topLeft.x and End.x<topLeft.x);
    }
    inline bool yCover(point &start,point &End)
    {
        return !(start.y>topRight.y and End.y>topRight.y) and !(start.y<bottomLeft.y and End.y<bottomLeft.y);
    }
};
struct line
{
    point start,End;
    double m,a;//y=mx-a
    friend istream& operator>>(istream& in,line &l)
    {
        in>>l.start>>l.End;
        l.BuildEquation();
        return in;
    }
    void BuildEquation()
    {
        if(start.x==End.x)
            m=0x3fffffff;
        else
            m=(start.y-End.y)/(start.x-End.x);
        a=m*start.x-start.y;//a=mx-y
    }
    double equation(point &p)
    {
        return m*p.x-p.y;
    }
    bool intersect(rectangle &rec)
    {
        if(!rec.xCover(start,End) or !rec.yCover(start,End))
            return false;
        if(m==0x3fffffff) return true;
        double e1,e2,e3,e4;
        e1=equation(rec.topLeft);
        e2=equation(rec.topRight);
        e3=equation(rec.bottomLeft);
        e4=equation(rec.bottomRight);
        bool positive,negative;//判斷四個頂點是否在線段左右
        positive=e1>=a or e2>=a or e3>=a or e4>=a;
        negative=e1<=a or e2<=a or e3<=a or e4<=a;
        return positive and negative;
    }
};
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        line l;
        rectangle rec;
        cin>>l>>rec;
        cout<<(l.intersect(rec) ? 'T':'F')<<endl;
    }
    return 0;
}

--------------------------------------------------

input.txt
output.txt