FZU 2273 Triangles

  • 2018-09-08
  • 40
  • 0

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

题目链接

给出两个三角形分别三个顶点的坐标位置判断两个三角的位置关系(相交、相离、包含)。

  1. 判断两三角形是否有相交的边,若有则可能的位置关系为包含或者相交
  2. 判断一个三角形顶点(三个)是否在另一三角形内部,若全在则位置关系为包含,若全不在则为相离,若不全在则相交

判断边是否相交的方式:叉乘

判断一点是否在三角形内部的方式:枚举三角形三个顶点,做此顶点上两条边的射线,连接判断点与顶点,通过叉乘判断此线段是否在两射线之间,若对于三个顶点都满足则此判断点在三角形内部,否则不在。

AC代码:

评论

还没有任何评论,你来说两句吧