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:
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.
从笛卡尔平面中随机选择三个不同的点，其坐标均满足-1000 ≤ x, y ≤ 1000，这三个点构成一个三角形。
考虑下面两个三角形：
可以验证三角形ABC包含原点，而三角形XYZ不包含原点。
在27K的文本文件triangles.txt（右击并选择“目标另存为……”）中包含了一千个“随机”三角形的坐标，找出其中包含原点在其内部的三角形的数量。
注意：文件中的前两个三角形就是上述样例。
解题
考虑了一下原点在三角形内部的三角形，原点到两个边的夹角应该有两个钝角，但是发现结果是510，表示不对，我是根据余弦定理就得costheta 这里有问题在实际中可能出现多于90度的情况然而在我计算中，我不知道怎么判断。还有个问题就是不知道我的这个想法是否有问题，下面的程序是不对的，留在这里待更改。
package Level4; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; public class PE0102{ public static void run(){ int count = 0; ArrayList<int[]> list = readData(); for(int i=0;i<list.size();i++){ int arr[] = list.get(i); if(iscontainmentTriangle(arr)){ count+=1; } if(i<10) System.out.println(iscontainmentTriangle(arr)); } System.out.println(count); } // 判断原点是否在三角形内部 public static boolean iscontainmentTriangle(int[] arr){ int count =0; for(int i=0;i<arr.length-1;i+=2){ int x1 = arr[i]; int y1 = arr[i+1]; for(int j=i+2;j<arr.length-1;j+=2){ int x2 = arr[j]; int y2 = arr[j+1]; if(isObtuseAngle(x1,y1,x2,y2)) count ++; if(count ==2) return true; } } return false; } // 是不是钝角 public static boolean isObtuseAngle(int x1,int y1,int x2,int y2){ long costheta = x1*y1 + x2*y2; if(costheta <0) return true; return false; } // 转换成整型数组 public static int [] StringtoInt(String[] strArr){ int[] IntArr = new int[strArr.length]; for(int i=0;i<strArr.length;i++) IntArr[i] = Integer.parseInt(strArr[i]); return IntArr; } // 读取数据 public static ArrayList<int[]> readData(){ String filename= "src/Level4/p102_triangles.txt"; ArrayList<int[]> list = new ArrayList<int[]>(); try { BufferedReader bufferedReader = new BufferedReader(new FileReader(filename)); String line = ""; while((line=bufferedReader.readLine())!=null){ String[] strArr = line.split(","); list.add(StringtoInt(strArr)); } } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return list; } public static void main(String[] args){ long t0 = System.currentTimeMillis(); run(); long t1 = System.currentTimeMillis(); long t = t1 - t0; System.out.println("running time="+t/1000+"s"+t%1000+"ms"); } }
mathblog 中提到了根据三角形面积相等的方式求解，ABC = ABO + ACO +BCO
这里我们知道了三角形的三个点如何根据这三个点求面积，看了下面求解的方式，根据两个向量可以快速的求出向量所组成三角形的面积S= 向量交叉相乘差的绝对值的二分之一
wiki 中有说明
Java
package Level4; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; public class PE0102{ public static void run(){ int count = 0; ArrayList<int[]> list = readData(); for(int i=0;i<list.size();i++){ int arr[] = list.get(i); if(iscontainmentTria(arr)){ count+=1; } } System.out.println(count); // 228 // running time=0s16ms } // 判断原点是否在三角形内部 public static boolean iscontainmentTria(int[] arr){ int area = 0; int count =0; int X1 = arr[0] - arr[2]; int Y1 = arr[1] - arr[3]; int X2 = arr[4] - arr[2]; int Y2 = arr[5] - arr[3]; int area2 = area(X1,Y1,X2,Y2); for(int i=0;i<arr.length-1;i+=2){ int x1 = arr[i]; int y1 = arr[i+1]; for(int j=i+2;j<arr.length-1;j+=2){ int x2 = arr[j]; int y2 = arr[j+1]; area +=area(x1,y1,x2,y2); } } if(area == area2) return true; return false; } // 这里面积的二倍 public static int area(int X1,int Y1,int X2,int Y2){ int area = Math.abs(X1*Y2 - X2*Y1); return area; } // 转换成整型数组 public static int [] StringtoInt(String[] strArr){ int[] IntArr = new int[strArr.length]; for(int i=0;i<strArr.length;i++) IntArr[i] = Integer.parseInt(strArr[i]); return IntArr; } // 读取数据 public static ArrayList<int[]> readData(){ String filename= "src/Level4/p102_triangles.txt"; ArrayList<int[]> list = new ArrayList<int[]>(); try { BufferedReader bufferedReader = new BufferedReader(new FileReader(filename)); String line = ""; while((line=bufferedReader.readLine())!=null){ String[] strArr = line.split(","); list.add(StringtoInt(strArr)); } } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return list; } public static void main(String[] args){ long t0 = System.currentTimeMillis(); run(); long t1 = System.currentTimeMillis(); long t = t1 - t0; System.out.println("running time="+t/1000+"s"+t%1000+"ms"); } }
Python
# coding=gbk import time as time import re import math import numpy as np def run(): filename = 'E:/java/projecteuler/src/Level4/p102_triangles.txt' mat = readData(filename) mat = np.array(mat) count = 0 for line in mat: if isContainmentTraingle(line): count+=1 print count def isContainmentTraingle(triangle): X1 = triangle[0] - triangle[2] Y1 = triangle[1] - triangle[3] X2 = triangle[4] - triangle[2] Y2 = triangle[5] - triangle[3] S = area(X1,Y1,X2,Y2) for i in range(0,4,2): for j in range(i+2,5,2): S -= area(triangle[i],triangle[i+1],triangle[j],triangle[j+1]) return S == 0 def area(x1,y1,x2,y2): S = np.abs(x1*y2 - x2*y1) return S def readData(filename): mat = list() file = open(filename) for line in file: row = line.split(',') row = [int(x) for x in row] mat.append(row) return mat t0 = time.time() run() t1 = time.time() print "running time=",(t1-t0),"s"