关于判断线段相交,具体算法见 点击打开链接 ,先进行快速排斥试验,若不能判断出两个线段不相交,再进行跨立试验。
//吐槽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"); } }