1016-德莱联盟

内存限制:64MB 时间限制:1000ms 特判: No
通过数:9 提交数:9 难度: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
 
参考链接：https://www.cnblogs.com/sytu/articles/3876585.html
这个是线段判交问题，其实线段重合符合这个题的要求。同时需要先进行快速排斥实验，先将两条会在同一条直线上的线段并不重合的情况排除，比如（0 0 1 1 2 2 3 3）这个情况。然后进行跨立实验。并不相交和重合的线段排除。
C++代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct Point{

    double x1,y1,x2,y2;

}point[];

int cmp(const Point& a,const Point& b){

    double k1 = (a.x2 - a.x1)*(b.y1 - a.y1) - (b.x1 - a.x1)*(a.y2 - a.y1);

    double k2 = (a.x2 - a.x1)*(b.y2 - a.y1) - (b.x2 - a.x1)*(a.y2 - a.y1);

    if(k1 * k2 <= ){    //k1*k2 == 0是指的是线段重合。

        return true;

    }

    else{

        return false;

    }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&point[].x1,&point[].y1,

                                         &point[].x2,&point[].y2,

                                         &point[].x1,&point[].y1,

                                         &point[].x2,&point[].y2);

        //快速排斥实验。 只要其中一个为真，那两条线段一定不相交。

        if(!(max(point[].x1,point[].x2) < min(point[].x1,point[].x2) ||

             max(point[].y1,point[].y2) < min(point[].y1,point[].y2) ||

             max(point[].x1,point[].x2) < min(point[].x1,point[].x2) ||

             max(point[].y1,point[].y2) < min(point[].y1,point[].y2))){

            if(cmp(point[],point[]) && cmp(point[],point[])){

                printf("Interseetion\n");

            }

            else{

                printf("Not Interseetion\n");

            }

        }

        else{

            printf("Not Interseetion\n");

        }

    }

    return ;

}

请使用手机"扫一扫"x

巴特西

(线段判交的一些注意。。。)nyoj 1016-德莱联盟

1016-德莱联盟

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章