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.

Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
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 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);
}

{
//p102_triangles.txt位于电脑中的路径
String path="C:\\Users\\wby\\Desktop\\p102_triangles.txt";
String [][] temp=new String[1][1];//暂存从文件中读取的数据
List<String> lines=null;
try {
temp=new String[lines.size()][];//初始化temp大小
new FileInputStream(path), "utf8"));
String str = "";
int i=0;
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