德莱联盟（判断两个线段是否相交）

矫情吗；* 2022-08-02 06:04 176阅读 0赞

## 德莱联盟 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 1

描述

欢迎来到德莱联盟。。。。

德莱文。。。

德莱文在逃跑，卡兹克在追。。。。

我们知道德莱文的起点和终点坐标，我们也知道卡兹克的起点和中点坐标，问：卡兹克有可能和德莱文相遇吗？，并且保证他们走的都是直线。

输入

几组数据，一个整数T表示T组数据  
每组数据 8个实数，分别表示德莱文的起点和终点坐标，以及卡兹克的起点和终点坐标

输出

如果可能 输出 Interseetion,否则输出 Not Interseetion

样例输入

2
    -19.74 7.14 22.23 -27.45 -38.79 -5.08 47.51 34.01
    -8.61 9.91 -32.47 6.47 -3.81 -16.1 7.82 -6.37

样例输出

Interseetion
    Not Interseetion

来源

[原创][Link 1]

上传者

[ACM\_王亚龙][ACM]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    typedef struct point
    {
        float x;
        float y;
    }Point;
    //判断直线AB是否与线段CD相交
    bool lineIntersectSide(Point A, Point B, Point C, Point D)
    {
        // A(x1, y1), B(x2, y2)的直线方程为：
        // f(x, y) =  (y - y1) * (x1 - x2) - (x - x1) * (y1 - y2) = 0
    
        float fC = (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y);
        float fD = (D.y - A.y) * (A.x - B.x) - (D.x - A.x) * (A.y - B.y);
    
        if(fC * fD > 0)
            return false;
    
        return true;
    }
    bool sideIntersectSide(Point A, Point B, Point C, Point D)
    {
        if(!lineIntersectSide(A, B, C, D))
            return false;
        if(!lineIntersectSide(C, D, A, B))
            return false;
        return true;
    }
    int main()
    {
        int n;
        Point a,b,c,d;
        cin>>n;
        while(n--)
        {
            cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
            if(sideIntersectSide(a,b,c,d))
            {
                cout<<"Interseetion"<<endl;
            }
            else
            {
                cout<<"Not Interseetion"<<endl;
            }
        }
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E5%8E%9F%E5%88%9B
[ACM]: http://acm.nyist.net/JudgeOnline/profile.php?userid=ACM_%E7%8E%8B%E4%BA%9A%E9%BE%99