51nod_1264:线段相交(计算几何)

时间:2023-03-08 22:00:55

题目链接

关于判断线段相交,具体算法见 点击打开链接 ,先进行快速排斥试验,若不能判断出两个线段不相交,再进行跨立试验。

//吐槽1,long long 会溢出。。。

//吐槽2,只进行跨立试验的虽然也可以ac,然而并不能解决两线段共直线且不相交的情况

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double LL;

struct point
{
    LL x,y;
    point operator -(const point& rhs)
    {
        point ret;
        ret.x=x-rhs.x;
        ret.y=y-rhs.y;
        return ret;
    }
    LL operator *(const point& rhs)//“叉乘”
    {
        return x*rhs.y-y*rhs.x;
    }
} a[];

bool nok1()
{
    ].x,a[].x)<min(a[].x,a[].x)||min(a[].x,a[].x)>max(a[].x,a[].x))\
           &&(max(a[].y,a[].y)<min(a[].y,a[].y)||min(a[].y,a[].y)>max(a[].y,a[].y));
}
bool ok2(point a,point b,point c,point d)
{
    ;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ; i<; i++)
            cin>>a[i].x>>a[i].y;
        if(nok1())
            puts("No");
        ],a[],a[],a[]) && ok2(a[],a[],a[],a[]))
            puts("Yes");
        else puts("No");
    }
}