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

fzu 2273 Triangles 计算几何

程序员文章站 2022-04-01 16:08:48
...

Problem 2273 Triangles

Time Limit: 1000 mSec    Memory Limit : 262144 KB

fzu 2273 Triangles 计算几何 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.)

fzu 2273 Triangles 计算几何 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

fzu 2273 Triangles 计算几何 Output

For each test case, output “intersect”, “contain” or “disjoint”.

fzu 2273 Triangles 计算几何 Sample Input

20 0 0 1 1 0 10 10 9 9 9 100 0 1 1 1 0 0 0 1 1 0 1

fzu 2273 Triangles 计算几何 Sample Output

disjoint intersect

fzu 2273 Triangles 计算几何 Source

第八届福建省大学生程序设计竞赛-重现赛(感谢承办方厦门理工学院)
import java.io.BufferedInputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		new Task().solve();
	}
}


class Task {
	Scanner in = new Scanner(new BufferedInputStream(System.in)) ;
	PrintWriter out = new PrintWriter(System.out);
	
	
	void solve(){
		int t = in.nextInt() ;
		in.nextLine() ;
		while(t-- > 0){
			List<Point> pa = new ArrayList<Point>(3) ;
			List<Point> pb = new ArrayList<Point>(3) ;
			for(int i = 0 ; i < 3 ; i++){
				pa.add(new Point(in.nextDouble() , in.nextDouble())) ;
			}
			for(int i = 0 ; i < 3 ; i++){
				pb.add(new Point(in.nextDouble() , in.nextDouble())) ;
			}
			Poly A = new Poly(pa) ;
			Poly B = new Poly(pb) ;
			if(A.polyintersec(B)){
				out.println("intersect") ;
			}
			else if(A.contain(B)){
				out.println("contain") ;
			}
			else{
				out.println("disjoint") ;
			}
		}
		out.flush() ;
	}
	
}

  
class Point{  
	   final double eps = 1e-10 ;  
	   double add(double x , double y){  
		     return Math.abs(x + y) < eps * (Math.abs(x) + Math.abs(y)) ? 0 : x+y ;  
	   }  
       double x , y ;  
       Point(){}  
       Point(double x , double y){
    	   this.x = x ;
    	   this.y = y ;
       }
       Point sub (Point o){  
             return new Point(add(x , -o.x) , add(y , -o.y)) ;  
       }  
       Point add (Point o){  
             return new Point(add(x , o.x) , add(y , o.y)) ;  
       }  
       double cross (Point o){  
             return x * o.y - y * o.x ;  
       }  
}
  
class  Poly{  
	final double eps = 1e-10 ;  
	int sign(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}
	
	boolean   onseg(Point p1 ,Point p2 , Point q){  
  	      return   sign( (p1.sub(q)).x * (p2.sub(q)).x ) <= 0  
  	            && sign( (p1.sub(q)).y * (p2.sub(q)).y ) <= 0 ;  
  	}
  	  
  	//判断线段p1p2, 线段q1q2是否相交  
  	boolean   intersection(Point p1 , Point p2 ,Point q1 , Point q2){  
  	      double d1 = (p2.sub(p1)).cross(q1.sub(p1)) ;  
  	      double d2 = (p2.sub(p1)).cross(q2.sub(p1)) ;  
  	      double d3 = (q2.sub(q1)).cross(p1.sub(q1)) ;  
  	      double d4 = (q2.sub(q1)).cross(p2.sub(q1)) ;  
  	      if(d1 == 0 && onseg(p1 , p2 , q1)) return true ;  
  	      if(d2 == 0 && onseg(p1 , p2 , q2)) return true ;  
  	      if(d3 == 0 && onseg(q1 , q2 , p1)) return true ;  
  	      if(d4 == 0 && onseg(q1 , q2 , p2)) return true ;  
  	      if(d1 * d2 < 0 && d3 * d4 < 0) return true ;  
  	      return false ;  
  	}  
  	
  	class Segline{
	      Point s , t ;  
	      Segline(Point s , Point t){
	    	  this.s = s ;
	    	  this.t = t ;
	      }  
	      boolean  segintersec(Segline o){  
	           return intersection(s , t , o.s , o.t) ;  
	      }  
	}
  	
    List<Point> lispoint ;  
    public Poly(List<Point> lispoint) {
    	this.lispoint = lispoint ; 
	}
    boolean  polyintersec(Poly o){  
           for(int i = 0 ; i < lispoint.size() ; i++){  
               Segline a = new Segline(lispoint.get(i) , lispoint.get((i+1)%o.lispoint.size())) ;  
               for(int j = 0 ; j < o.lispoint.size() ; j++){  
                   Segline b = new Segline(o.lispoint.get(j) , o.lispoint.get((j+1)%o.lispoint.size())) ;  
                   if(a.segintersec(b))  return true ;  
               }  
           }  
           return false  ;  
   }
    
   boolean contain(Poly o){
	   int in = 0 ;
	   for(int i = 0 ; i < lispoint.size() ; i++){  
          if(inConvexPolygon(o.lispoint, lispoint.get(i))){
        	  in++ ;
          }
       }  
	   if(in == lispoint.size()){
		   return true ;
	   }
	   
	   in = 0 ;
	   for(int i = 0 ; i < o.lispoint.size() ; i++){  
          if(inConvexPolygon(lispoint , o.lispoint.get(i))){
        	  in++ ;
          }
       }  
	   if(in == o.lispoint.size()){
		   return true ;
	   }
	   return false ;
   } 
    
    boolean inConvexPolygon(List<Point> p, Point target) {  
    	    int flag= sign( (p.get(0).sub(target)).cross( p.get(1).sub(target) ) ) ;  
    	    for(int i = 1 ; i < p.size() ; i++)  
    	    {  
    	        if(sign( (p.get(i).sub(target)).cross( p.get((i+1)%p.size()).sub(target) ) ) !=flag)  
    	            return false ;  
    	    }  
    	    return true ;  
    }   
    
}