福建省第八届 Triangles

Problem Description

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.)

Input

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6. All the coordinate are integer. (X1,Y1) , (X2,Y2), (X3,Y3) forms triangles A ; (X4,Y4) , (X5,Y5), (X6,Y6) forms triangles B.

-10000<=All the coordinate <=10000

Output

For each test case, output “intersect”, “contain” or “disjoint”.

Sample Input

2 0 0 0 1 1 0 10 10 9 9 9 10 0 0 1 1 1 0 0 0 1 1 0 1

Sample Output

disjoint

intersect

判断两个三角形是相交，包含，还是相离的关系

包含关系：

如图：若ΔDEF被包含；则可通过点来判断

D点被包含SΔACD+SΔCDB+SΔADB=SΔABC 同理判断E、F点，若三点全满足则包含

相离关系：

如图：若D点在外：则有SΔDAC+SΔDBC+SΔAB>SΔABC

若三点都满足上式，则相离，剩下的就只有相交关系了。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
int t,ans;
struct point
{
    double x;
    double y;
};
struct trangle
{
    point p[3];
}angle[2];
double area(point a,point b,point c)
{
    return fabs((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));//三角形面积
}
bool check(trangle a,trangle b)
{
    double area_trangle=area(a.p[0],a.p[1],a.p[2]);//判断是否包含和不相交
    int pos=0;
    for(int i=0;i<3;i++)
    {
        if((area(b.p[i],a.p[0],a.p[1])+area(b.p[i],a.p[1],a.p[2])+area(b.p[i],a.p[0],a.p[2]))>area_trangle) continue;
        else ans++,pos++;
    }
    return pos==3;
}
void solve()
{
    ans=0;
    if(check(angle[0],angle[1]) || check(angle[1],angle[0]))
    {
        puts("contain");
        return ;
    }
    else if(!ans)
    {
        puts("disjoint");
        return ;
    }
    else
    {
        puts("intersect");
        return ;
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<3;j++)
            {
                scanf("%lf%lf",&angle[i].p[j].x,&angle[i].p[j].y);
            }
        }
        solve();
    }
    return 0;
}