欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Triangles FZU - 2273

程序员文章站 2022-04-01 16:08:54
...

This is a simple problem. Given two triangles A and B, you should determine they are intersect, contain or disjoint. (Public edge or point are treated as intersect.)

判断点包含在多边形内:
如果点x在三角形b内,则点x与b上的其它点组成的三角形的面积的总和小于等于三角形的b的面积
判断线段相交:
如果一个点与直接上任意两个点组成的向量的叉积为正则点在直线顺时针方向,否则点在直线的逆时针方向
t1t2判断点c、d是否一个在直线ab的顺时针方向,一个在直线ab的逆时针方向,
如果成立,则说明线段cd与直线ab相交,t3
t4同理
如果线段ab与直线cd相交,并且线段cd与直线ab相交,则说明线段ab与线段cd相交

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
struct point
{
    ll x,y;
}a[3],b[3];
ll cal(point x,point y,point z)
{
    return abs(x.x*y.y-x.y*y.x+y.x*z.y-y.y*z.x+z.x*x.y-z.y*x.x);
}
bool in(point x)
{
    ll s=cal(b[0],b[1],b[2]),sx=cal(b[0],b[1],x),sy=cal(b[1],b[2],x),sz=cal(b[0],b[2],x);
    return sx+sy+sz<=s;
}
/*
如果点x在三角形b内,则点x与b上的其它点组成的三角形的面积的总和小于等于三角形的b的面积
*/
ll dis(point x,point y,point z)//计算向量zy和zx的叉积
{
    return (z.x-y.x)*(z.y-x.y)-(z.y-y.y)*(z.x-x.x);
}
bool Intersec(point a,point b,point c,point d)
{
    ll t1=dis(a,b,c),t2=dis(a,b,d),t3=dis(c,d,a),t4=dis(c,d,b);
    return t1*t2<=0&&t3*t4<=0;
}
/*
叉积为正则点在线段顺时针方向,否则在线段的逆时针方向
t1*t2判断点c、d是否一个在直线ab的顺时针方向,一个在直线ab的逆时针方向,
如果成立,则说明线段cd与直线ab相交,t3*t4同理
如果线段ab与直线cd相交,并且线段cd与直线ab相交,则说明线段ab与线段cd相交
*/
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<3;i++)
            scanf("%lld%lld",&a[i].x,&a[i].y);
        for(int i=0;i<3;i++)
            scanf("%lld%lld",&b[i].x,&b[i].y);
        int flag=3;
        if(in(a[0])&&in(a[1])&&in(a[2])) flag=2;
        for(int i=0;i<3;i++)
            swap(a[i],b[i]);
        if(in(a[0])&&in(a[1])&&in(a[2])) flag=2;
        if(Intersec(a[0],a[1],b[0],b[1])||Intersec(a[0],a[2],b[0],b[1])||Intersec(a[1],a[2],b[0],b[1])||Intersec(a[0],a[1],b[0],b[2])||Intersec(a[0],a[2],b[0],b[2])||Intersec(a[1],a[2],b[0],b[2])||Intersec(a[0],a[1],b[1],b[2])||Intersec(a[0],a[2],b[1],b[2])||Intersec(a[1],a[2],b[1],b[2])) flag=1;
        if(flag==3) printf("disjoint\n");
        else if(flag==2) printf("contain\n");
        else printf("intersect\n");
    }
}