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相交,t3t4同理
如果线段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");
}
}
推荐阅读
-
FZU - 2295 Human life (最大权闭合子图)
-
FZU2018级算法第一次作业 1.1fibonacci (矩阵快速幂)
-
kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150
-
codeforces C. Count Triangles
-
codeforces 643 C - Count Triangles
-
Codeforces 1355 C. Count Triangles
-
POJ 1471Triangles
-
P6143 [USACO20FEB]Equilateral Triangles P——几何+二维前缀和
-
Nested Triangles 2018 ACM-ICPC中国大学生程序设计竞赛
-
Triangles(贪心、模拟)