题目102：文件中的三角形中有多少个内部包含原点？
Triangle containmentThree 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.
题目：
在笛卡尔平面上随机取三个不同的点，其中 -1000 ≤ x, y ≤ 1000，会形成一个三角形。
考虑如下两个三角形：
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
可以证明三角形 ABC 包含原点在其内部，而三角形 XYZ 则不包含。
包含一千个随机三角形，求其中有多少个三角形的内部包含原点。
注意：文件中的前两个三角形即为上述例子中的三角形。
这题的思路是利用同向法求点是否包含在三角形内部：
http://pic002.cnblogs.com/img/zdd/201008/2010080517445256.png
假设点P位于三角形内，会有这样一个规律，当我们沿着ABCA的方向在三条边上行走时，你会发现点P始终位于边AB，BC和CA的右侧。我们就利用这一点，但是如何判断一个点在线段的左侧还是右侧呢？我们可以从另一个角度来思考，当选定线段AB时，点C位于AB的右侧，同理选定BC时，点A位于BC的右侧，最后选定CA时，点B位于CA的右侧，所以当选择某一条边时，我们只需验证点P与该边所对的点在同一侧即可。问题又来了，如何判断两个点在某条线段的同一侧呢？
两点p1(x1,y1),p2(x2,y2),判断点p(x,y)在线的左边还是右边：
Tmp = (y1 – y2) * x + (x2 – x1) * y + x1 * y2 – x2 * y1
Tmp > 0 在左侧
Tmp = 0 在线上
Tmp < 0 在右侧
所以，有了方法写程序就很简单了：
# -*- coding: utf-8 -*-
"""
Created on Sat Jan7 09:41:55 2017
@author: Jerry Xu
"""
def tend(a,b,p):
x1,y1 = a
x2,y2 = b
x, y= p
return (y1-y2)*x + (x2-x1)*y + x1*y2 -x2*y1
def judge(a,b,c):
d1 = tend(a,b,(0,0))
d2 = tend(b,c,(0,0))
d3 = tend(c,a,(0,0))
if (d1>0 and d2>0 and d3>0) or (d1<0 and d2<0 and d3<0): #我们只需判断是否同向即可，都左或者都右都可以。
return True
else:
return False
c = 0
with open('p102_triangles.txt') as f:
lines = f.readlines()
for line in lines:
line = line.strip('\n').split(',')
A = (int(line),int(line))
B = (int(line),int(line))
C = (int(line),int(line))
if judge(A,B,C):
c += 1
print (c)
输出：
228 # encoding:utf-8
# 面积法
from time import time
from math import sqrt
P = (0, 0)
def calArea(A, B, C):
a = sqrt((A - B) ** 2 + (A - B) ** 2)
b = sqrt((A - C) ** 2 + (A - C) ** 2)
c = sqrt((B - C) ** 2 + (B - C) ** 2)
p = (a + b + c) / 2
return sqrt(p * (p - a) * (p - b) * (p - c))
def isInTri(points):
A, B, C = (points, points), (points, points), (points, points)
area_ac = calArea(P, A, C)
area_bc = calArea(P, B, C)
area_ab = calArea(P, A, B)
area_bac = calArea(A, B, C)
if abs(area_ac + area_ab + area_bc - area_bac) < 0.00001:
return True
def euler102():
count = 0
with open('p102_triangles.txt') as file:
for line in file:
points =
if isInTri(points):
print(points)
count += 1
print(count)
if __name__ == '__main__':
start = time()
euler102()
print('cost %.6f sec' % (time() - start))
228
cost 0.058000 sec # encoding:utf-8
# 重心法
from time import time
class Vector2:
def __init__(self, t):
self.x = t
self.y = t
def minus(self, t):
return Vector2((self.x - t.x, self.y - t.y))
def dot(self, t):
return self.x * t.x + self.y * t.y
P = Vector2((0, 0))
def isInTri(A, B, C):
v0 = C.minus(A)
v1 = B.minus(A)
v2 = P.minus(A)
dot00 = v0.dot(v0)
dot01 = v0.dot(v1)
dot02 = v0.dot(v2)
dot11 = v1.dot(v1)
dot12 = v1.dot(v2)
div = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * div
if u <= 0 or u >= 1:
return False
v = (dot00 * dot12 - dot01 * dot02) * div
if v <= 0 or v >= 1:
return False
return u + v < 1
def euler102():
count = 0
with open('p102_triangles.txt') as file:
for line in file:
tmp = line.replace('\n', '').split(',')
A = Vector2((int(tmp), int(tmp)))
B = Vector2((int(tmp), int(tmp)))
C = Vector2((int(tmp), int(tmp)))
if isInTri(A, B, C):
print(tmp)
count += 1
print(count)
if __name__ == '__main__':
start = time()
euler102()
print('cost %.6f sec' % (time() - start)) 异端方法
https://i.loli.net/2021/07/18/3RitJX2wer16x5T.png 利用内积的性质。
/*
答案：228
*/
#include <cstdio>
int main(void)
{
errno_t err;
FILE *fp = NULL;
err = fopen_s(&fp, "p102_triangles.txt", "r");//打开文件
if (err != 0)
{
printf_s("数据文件未打开\n");
return 0;
}
int x, y;
int nCount = 0;
while (fscanf_s(fp, "%d,%d,%d,%d,%d,%d", &x, &y, &x, &y, &x, &y) != EOF)
{
int d1 = x * y - x * y;
int d2 = x * y - x * y;
int d3= x * y - x * y;
if (d1 > 0 && d2 > 0 && d3 > 0 || d1 < 0 && d2 < 0 && d3 < 0)
++nCount;
}
fclose(fp);
printf_s("%d\n", nCount);
return 0;
}
页:
[1]