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

FZU2273:Triangles(计算几何 & 两三角形的位置)

程序员文章站 2022-04-01 16:11:53
...

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 

题意:给两个三角形,判断他们的位置关系,相交相离或包含。

思路:判相交通过判断线段相交情况即可。至于相离还是包含,判断三个点是否都在三角形内就行了(用叉积比较面积的关系),或者判断一下有几个点在凸包上,或者用这个点击打开链接

凸包方法:

# include <iostream>
# include <cstdio>
# include <cmath>
# include <algorithm>
using namespace std;
struct node
{
    double x, y;
}ta[3], tb[3], tc[8], ans[8];
inline node operator-(node a, node b)
{
    node tmp;
    tmp.x = a.x-b.x;
    tmp.y = a.y-b.y;
    return tmp;
}
inline double operator*(node a, node b){return a.x*b.y-a.y*b.x;}
inline double cha(node a, node b, node c) {return (a-b)*(a-c);}
inline double dis(node a) {return a.x*a.x+a.y*a.y;}
inline bool cmp(node x, node y)
{
    if(fabs((x-tc[1])*(y-tc[1]))>0) return (x-tc[1])*(y-tc[1])>0;
    return dis(x-tc[1])<dis(y-tc[1]);
}
bool fun(node a, node b, node c, node d)
{
    if((max(a.x,b.x)>=min(c.x,d.x) || max(c.x,d.x)>=min(a.x,b.x)) && (max(a.y,b.y)>=min(c.y,d.y) || max(c.y,d.y)>=min(a.y,b.y)))
    {
        double c1=cha(a,b,c), c2=cha(a,b,d), c3=cha(c,d,a), c4=cha(c,d,b);
        if(c1*c2<=0 && c3*c4<=0) return true;
        return false;
    }
    else return false;
}
bool cal(node a, node b)
{
    for(int i=0; i<3; ++i) if(fun(a, b, tb[i], tb[(i+1)%3])) return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0; i<3; ++i) scanf("%lf%lf",&ta[i].x, &ta[i].y);
        for(int i=0; i<3; ++i) scanf("%lf%lf",&tb[i].x, &tb[i].y);
        int flag = 0;
        flag |= cal(ta[0], ta[1]);
        flag |= cal(ta[1], ta[2]);
        flag |= cal(ta[0], ta[2]);
        if(flag) puts("intersect");
        else
        {
            int cnt = 0;
            for(int i=0; i<3; ++i) tc[++cnt] = ta[i];
            for(int i=0; i<3; ++i) tc[++cnt] = tb[i];
            for(int i=2;i<=cnt;i++)
                if(tc[i].y<tc[1].y||(tc[i].y==tc[1].y&&tc[i].x<tc[1].x))
                    swap(tc[1],tc[i]);
            sort(tc+2,tc+cnt+1,cmp);
            int top=2;ans[1]=tc[1];ans[2]=tc[2];
            for(int i=3; i<=cnt; ++i)
            {
                while(top>1&&(tc[i]-ans[top-1])*(ans[top]-ans[top-1])>=0) --top;
                ans[++top]=tc[i];
            }
            if(top == 3) puts("contain");
            else puts("disjoint");
        }
    }
    return 0;
}