51 Nod 1264線分交差

平面上の2つのセグメントの2つの端点を与え、2つのセグメントが交差しているかどうかを判断します(共通点があるか、部分的に一致して交差していると考えられています).交差する場合は「Yes」を出力し、そうでない場合は「No」を出力します.Input 1行目:1個数T、入力したテスト数(1<=T<=1000)2-T+1行目:1行あたり8個数、x 1、y 1、x 2、y 2、x 3、y 3、x 4、y 4を示す.(-10^8<=xi,yi<=10^8)(直線1の2つの端点がx 1,y 1|x 2,y 2,直線2の2つの端点がx 3,y 3|x 4,y 4)Outputは共にT行を出力し,交差出力が「Yes」である場合は「No」を出力する.Input例2 1 2 2 1 0 2 2-1 1 1 1 0 1-1 Output例Yes No

#include
#include
#include
#include
#define eps 1e-8
#define zero(x) ((x>0? x:-x)
using namespace std;
struct point
{
    double x,y;
};
struct line
{
    point a,b;
};
double xmult(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int dots_inline(point p1,point p2,point p3)
{
    return zero(xmult(p1,p2,p3));
}
int same_side(point p1,point p2,point l1,point l2)
{
    return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
int dot_online_in(point p,point l1,point l2)
{
    return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)int intersect_in(point u1,point u2,point v1,point v2)
{
    if(!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
        return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
    return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        point p1,p2,p3,p4;
        cin>>p1.x>>p1.y;
        cin>>p2.x>>p2.y;
        cin>>p3.x>>p3.y;
        cin>>p4.x>>p4.y;
        int flag=intersect_in(p1,p2,p3,p4);
        if(flag)
            cout<<"Yes"<else
            cout<<"No"<