fzu 2273 Triangles 计算几何
程序员文章站
2022-04-01 16:08:48
...
Problem 2273 Triangles
Time Limit: 1000 mSec Memory Limit : 262144 KB
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
20 0 0 1 1 0 10 10 9 9 9 100 0 1 1 1 0 0 0 1 1 0 1
Sample Output
disjoint intersect
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 ;
}
}