51Nod1264 线段相交

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

这道题用的了数学几何的一个知识点：向量的叉乘性质。

向量a×向量b（×为向量叉乘），若结果小于0，表示向量b在向量a的顺时针方向；若结果大于0，表示向量b在向量a的逆时针方向；若等于0，表示向量a与向量b平行。

比如线段ab与cd相交，ad×ab>0,ac×ab<0。

详解可以看看大神的博客：判断两条线段是否相交—(向量叉乘) - 特务依昂 -

AC代码如下：

#include <iostream>
using namespace std;
struct node
{
    double x,y;
}a,b,c,d;
void solve()
{
   double p[4];
    p[0]=(b.x-a.x)*(b.y-c.y)-(b.y-a.y)*(b.x-c.x); //ba X bc
    p[1]=(b.x-a.x)*(b.y-d.y)-(b.y-a.y)*(b.x-d.x); //ba X bd
    p[2]=(d.x-c.x)*(d.y-a.y)-(d.y-c.y)*(d.x-a.x);
    p[3]=(d.x-c.x)*(d.y-b.y)-(d.y-c.y)*(d.x-b.x);
    if ((p[0]*p[1]<=0)&&(p[2]*p[3]<=0))
      cout<<"YES"<<endl;
    else
         cout<<"NO"<<endl;
}  
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
        solve();
    }
    return 0;
}