线段与三角形-算法题

问题描述

给定线段PQ和三角形ABC，求三角形面积并确定线段PQ是否与三角形相交。

输入

有多组测试数据。输入的第一行上有正整数n，表示有n组测试数据。每组测试数据有2行：第一行上有6个整数x1 y1 x2 y2 x3 y3，整数之间用一个空格隔开，他们分别表示三角形ABC的三个顶点坐标A(x1，y1)、B(x2，y2)、C(x3，y3)；第二行是4个整数u v w t，整数之间用一个空格隔开，他们表示线段PQ端点P和Q的坐标P(u，v)，Q(w，t)。

输出

对输入中的每组测试数据，先输出一行，内容是“Case i:”，其中i是数组的编号（从1开始）。在下一行上输出三角形的面积（四舍五入保留1位小数），空一格后输出三角形与线段的相交情况：对给定的三角形ABC和线段PQ，如果线段PQ与三角形的边相交，那么输出“Yes”，否则输出“No”。约定：当线段PQ在三角形内部时，PQ与三角形的边不相交。

输入举例

2
0 0 4 4 0 4
1 2 1 3
0 0 3 4 0 4
0 -3 -1 -4

输出样例

Case 1:
8.0 No
Case 2:
6.0 No

public class Main {

	public static int direction(int[] pi, int[] pj, int[] pk){ 
        return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]); 
    } 
    /** 
     * 判断点pk是否在线段 pi,pj 上 
     * @return boolean 
     */
    public static boolean onSegment(int[] pi, int[] pj, int[] pk) { 
        if ( Math.min(pi[0], pj[0]) <= pk[0] && pk[0] <= Math.max(pi[0], pj[0]) &&  
             Math.min(pi[1], pj[1]) <= pk[1] && pk[1] <= Math.max(pi[1], pj[1]) ) { 
            return true; 
        }else { 
            return false; 
        } 
    } 
    // 判断线段 p1,p2 和线段 p3,p4 是否相交 
    public static boolean segmentInsert(int[] p1, int[] p2, int[] p3, int[] p4) { 
        int d1 = direction(p3, p4, p1); 
        int d2 = direction(p3, p4, p2); 
        int d3 = direction(p1, p2, p3); 
        int d4 = direction(p1, p2, p4); 
        if ( ((d1>0 && d2<0) || (d1<0 && d2>0)) && 
             ((d3>0 && d4<0) || (d3<0 && d4>0))) { 
            return true; 
        } else if ( d1==0 && onSegment(p3, p4, p1)) { 
            return true; 
        } else if ( d2==0 && onSegment(p3, p4, p2)) { 
            return true; 
        } else if ( d3==0 && onSegment(p1, p2, p3)) { 
            return true; 
        } else if ( d4==0 && onSegment(p1, p2, p4)) { 
            return true; 
        } else { 
            return false; 
        } 
    } 
    
    public static double area(int[] p1, int[] p2, int[] p3){
//    	return (p1[0]*p2[1]+p2[0]*p3[0]*p1[1] - p1[0]*p3[1] - p2[0]*p1[1] - p3[0]*p2[1])/2.0;
    	return Math.abs( Main.direction(p1, p2, p3)/2.0 );
    }
  
    public static void meet(int[] p1, int[] p2, int[] p3,int[] p4, int p5[],int n) {
    	double area = Main.area(p1, p2, p3);
    	System.out.println("Case "+n);
    	System.out.print(area);
    	boolean b1 = segmentInsert(p1, p2, p5, p4);
    	boolean b2 = segmentInsert(p1, p3, p5, p4);
    	boolean b3 = segmentInsert(p3, p2, p5, p4);
    	
    	if (b1 && b2 && b3) {
			System.out.println(" Yes");
		}else{
			System.out.println(" No");
		}
    	
	}
    
    public static void main(String[] args){ 
        Scanner in = new Scanner(System.in);    
        while(in.hasNext()){
        	int n = in.nextInt();
        	for (int i = 1; i <= n; i++) {
        		//三角形三点
        		int[] p1 = {in.nextInt(), in.nextInt()}; 
                int[] p2 = {in.nextInt(), in.nextInt()}; 
                int[] p3 = {in.nextInt(), in.nextInt()};
                int[] p4 = {in.nextInt(), in.nextInt()};
                int[] p5 = {in.nextInt(), in.nextInt()};
                Main.meet(p1, p2, p3, p4, p5, i);
			}
        }
    } 
}