德莱联盟

描述 

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

德莱文。。。

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

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

输入

几组数据，一个整数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

代码：

#include <iostream>
using namespace std;

int main() {
    
    //德莱文的起点与终点坐标
    double dex1, dey1, dex2, dey2;
    
    //卡兹克的起点与终点坐标
    double kax1, kay1, kax2, kay2;
    
    int n;
    cin >> n;
    while (n--) {
        cin >> dex1 >> dey1 >> dex2 >> dey2 >> kax1 >> kay1 >> kax2 >> kay2;
        //德莱文的斜率dek，常量b(直线的方程式y = kx + b)
        double dek, deb;
        dek = (dey2 - dey1) / (dex2 - dex1);
        deb = dey1 - dek * dex1;
        //卡兹克的斜率kak，常量b
        double kak, kab;
        kak = (kay2 - kay1) / (kax2 - kax1);
        kab = kay1 - kak * kax1;
        
        //因为不知道起点与终点的x的大小关系，所以需要先找出他们的大小关系，这里left指较小的x，right指较大的x
        double deLeftX, deRightX;
        double kaLeftX, kaRightX;
        if (dex1 > dex2) { //找出德莱文的左x和右x
            deLeftX = dex2;
            deRightX = dex1;
        } else {
            deLeftX = dex1;
            deRightX = dex2;
        }
        
        if (kax1 > kax2) { //找出卡兹克的左x和右x
            kaLeftX = kax2;
            kaRightX = kax1;
        } else {
            kaLeftX = kax1;
            kaRightX = kax2;
        }
        
        //如果这两个区间没有交集，那么这两条线段也就不可能相交
        if (deRightX < kaLeftX || kaRightX < deLeftX) {
            cout << "Not Interseetion" << endl;
            continue;
        }
        
        if (dek == kak) { //斜率相同，无交点
            cout << "Not Interseetion" << endl;
            continue;
        } else { //斜率不相同，判断两条线段是否相交
        
            double InterseetionX;
            //求出两条直线的交点
            InterseetionX = (kab - deb) / (dek - kak);
            //求出德莱文起点与终点区间与卡兹克起点与终点区间的交集
            
            double leftX, rightX;
            if (deLeftX > kaLeftX) {
                leftX = deLeftX;
            } else {
                leftX = kaLeftX;
            }
            if (deRightX > kaRightX) {
                rightX = kaRightX;
            } else {
                rightX = deRightX;
            }
            //判断直线的交点在不在公共区间内，如果两条直线的交点在这两个区间的公共区间内，那么线段肯定相交
            if (InterseetionX >= leftX && InterseetionX <= rightX) {
                cout << "Interseetion" << endl;
            } else {
                cout << "Not Interseetion" << endl;
            }
        }
    }
    return 0;
}

德莱联盟

原文：http://blog.csdn.net/bao_libra/article/details/51333569