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.)
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
For each test case, output “intersect”, “contain” or “disjoint”.
2 0 0 0 1 1 0 10 10 9 9 9 10 0 0 1 1 1 0 0 0 1 1 0 1Sample 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;
}