当前位置:首页 » Project Euler » 详细页

Triangle containment 题号:102 难度: 15 中英对照

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

Solution

题目要求txt文件给出的坐标构成的三角形中,有多少个三角形是包括原点的。 1. 首先,对于任一点(X,Y),如何判断点(X,Y)在三个点连线组成的三角形内部? 我们知道,三个点中任意两个点都可以组成一条直线,共三条直线,围成一个三角形。那么当点(X,Y)在这三条直线上,或者在三条直线的同一侧时,点(X,Y)即在三角形内部。 2. 其次,如何判断点(X,Y)在直线的某一侧? 点(X1,Y1)和点(X2,Y2)确定的直线A,点(X,Y)与直线A有三种关系:在直线A上,在直线A左边,在直线A右边。先考虑点(X,Y)在直线A上的情况。很容易得到以下两个方程(k为斜率): $$Y2-Y1=k(X2-X1)$$ $$Y-Y1=k(X-X1)$$ 两个方程上下相除得: $$(Y-Y1)(X2-X1)-(X-X1)(Y2-Y1)=0$$ 因此,对于三个点(X1,Y1),(X2,Y2),(X3,Y3),当$(Y-Yi)(Xj-Xi)-(X-Xi)(Yj-Yi)$都同号(在内部),或者至少一个为0(在直线上)时,点(X,Y)在这三直线的同一侧。即点(X,Y)在三角形内部

Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class p102 {
	public static void main(String[] args) 
	 {
	        long start=System.nanoTime();
	        long result = run();        
	        long end=System.nanoTime();
	        System.out.println(result);
	        System.out.println( (end-start)/1000000 + "ms" );
	 }	
	 public static long run()
	 {
		 int nums[][]=readFile();
		 int count=0;
		 for(int []n : nums)
		 {
			 
			 if(isInTriangle(n,0,0))
				 count++;
		 }
		 return count;
	 }
	 
	public static boolean isInTriangle(int[] t, int x, int y) {
		//a,b,c用来判断原点在直线的哪一侧。
		int a = Integer.signum((t[0] - t[2]) * (y - t[1]) - (t[1] - t[3]) * (x - t[0]));
		int b = Integer.signum((t[2] - t[4]) * (y - t[3]) - (t[3] - t[5]) * (x - t[2]));
		int c = Integer.signum((t[4] - t[0]) * (y - t[5]) - (t[5] - t[1]) * (x - t[4]));
		//如果点(0,0)在三条直线上,或者在三条直线的同一侧,则在三角形内部
		return a == 0 || b == 0 || c == 0 || (a == b && b == c);
	}
	 
	 public static int[][] readFile()
	 {
		//p102_triangles.txt位于电脑中的路径
		String path="C:\\Users\\wby\\Desktop\\p102_triangles.txt";
		String [][] temp=new String[1][1];//暂存从文件中读取的数据
		List<String> lines=null; 
		try {
	        lines = Files.readAllLines(Paths.get(path), StandardCharsets.UTF_8); //文件的总行数
	        temp=new String[lines.size()][];//初始化temp大小
	        BufferedReader reader = new BufferedReader(new InputStreamReader(  
	                new FileInputStream(path), "utf8"));  
	        String str = "";  
	        int i=0;
	        while ((str = reader.readLine()) != null) {  
	        	temp[i]=str.split(",");
	        	i++;
	        }
         } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
         } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
         }

		//String 数组转为 int数组,方便计算
		int [][] nums=new int[temp.length][temp[0].length];
		for(int i=0;i<temp.length;i++)
			for(int j=0;j<temp[0].length;j++)
				nums[i][j]=Integer.parseInt(temp[i][j]);
		return nums;
	 }
}
228
26ms