福建省第八届 Triangles-白红宇

福建省第八届 Triangles

阅读量：5295 次

发布时间：2019-06-14

本文共 1629 字，大约阅读时间需要 5 分钟。

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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;#define lowbit(x) (x&(-x))#define max(x,y) (x>y?x:y)#define min(x,y) (x
                
                 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;}

转载于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/7280906.html

你可能感兴趣的文章