题目102：文件中的三角形中有多少个内部包含原点？

欧拉计划

Triangle containment

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.

题目：

在笛卡尔平面上随机取三个不同的点，其中 -1000 ≤ x, y ≤ 1000，会形成一个三角形。

考虑如下两个三角形：

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

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

可以证明三角形 ABC 包含原点在其内部，而三角形 XYZ 则不包含。
p102_triangles.txt (25.76 KB, 下载次数: 26)

2016-8-17 18:07 上传

点击文件名下载附件

包含一千个随机三角形，求其中有多少个三角形的内部包含原点。

注意：文件中的前两个三角形即为上述例子中的三角形。

jerryxjr1220

这题的思路是利用同向法求点是否包含在三角形内部：

                               
登录/注册后可看大图

假设点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 在右侧

所以，有了方法写程序就很简单了：

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Sat Jan  7 09:41:55 2017
   
4. 
   
5. @author: Jerry Xu
   
6. """
   
7. 
   
8. def tend(a,b,p):
   
9.     x1,y1 = a
   
10.     x2,y2 = b
    
11.     x, y  = p
    
12.     return (y1-y2)*x + (x2-x1)*y + x1*y2 -x2*y1
    
13.    
    
14. def judge(a,b,c):
    
15.     d1 = tend(a,b,(0,0))
    
16.     d2 = tend(b,c,(0,0))
    
17.     d3 = tend(c,a,(0,0))
    
18.     if (d1>0 and d2>0 and d3>0) or (d1<0 and d2<0 and d3<0): #我们只需判断是否同向即可，都左或者都右都可以。
    
19.         return True
    
20.     else:
    
21.         return False
    
22. 
    
23. c = 0
    
24. with open('p102_triangles.txt') as f:
    
25.     lines = f.readlines()
    
26. for line in lines:
    
27.     line = line.strip('\n').split(',')
    
28.     A = (int(line[0]),int(line[1]))
    
29.     B = (int(line[2]),int(line[3]))
    
30.     C = (int(line[4]),int(line[5]))
    
31.     if judge(A,B,C):
    
32.         c += 1
    
33. print (c)

复制代码

输出：
228

芒果加黄桃

1. # encoding:utf-8
   
2. # 面积法
   
3. from time import time
   
4. from math import sqrt
   
5. P = (0, 0)
   
6. def calArea(A, B, C):
   
7.     a = sqrt((A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2)
   
8.     b = sqrt((A[0] - C[0]) ** 2 + (A[1] - C[1]) ** 2)
   
9.     c = sqrt((B[0] - C[0]) ** 2 + (B[1] - C[1]) ** 2)
   
10.     p = (a + b + c) / 2
    
11.     return sqrt(p * (p - a) * (p - b) * (p - c))
    
12. def isInTri(points):
    
13.     A, B, C = (points[0], points[1]), (points[2], points[3]), (points[4], points[5])
    
14.     area_ac = calArea(P, A, C)
    
15.     area_bc = calArea(P, B, C)
    
16.     area_ab = calArea(P, A, B)
    
17.     area_bac = calArea(A, B, C)
    
18.     if abs(area_ac + area_ab + area_bc - area_bac) < 0.00001:
    
19.         return True
    
20. def euler102():
    
21.     count = 0
    
22.     with open('p102_triangles.txt') as file:
    
23.         for line in file:
    
24.             points = [int(x) for x in line.replace('\n', '').split(',')]
    
25.             if isInTri(points):
    
26.                 print(points)
    
27.                 count += 1
    
28.     print(count)
    
29. if __name__ == '__main__':
    
30.     start = time()
    
31.     euler102()
    
32.     print('cost %.6f sec' % (time() - start))
    

复制代码

228
cost 0.058000 sec

芒果加黄桃

1. # encoding:utf-8
   
2. # 重心法
   
3. from time import time
   
4. class Vector2:
   
5.     def __init__(self, t):
   
6.         self.x = t[0]
   
7.         self.y = t[1]
   
8.     def minus(self, t):
   
9.         return Vector2((self.x - t.x, self.y - t.y))   
   
10.     def dot(self, t):
    
11.         return self.x * t.x + self.y * t.y
    
12. P = Vector2((0, 0))
    
13. def isInTri(A, B, C):
    
14.     v0 = C.minus(A)
    
15.     v1 = B.minus(A)
    
16.     v2 = P.minus(A)
    
17.     dot00 = v0.dot(v0)
    
18.     dot01 = v0.dot(v1)
    
19.     dot02 = v0.dot(v2)
    
20.     dot11 = v1.dot(v1)
    
21.     dot12 = v1.dot(v2)
    
22.     div = 1 / (dot00 * dot11 - dot01 * dot01)
    
23.     u = (dot11 * dot02 - dot01 * dot12) * div
    
24.     if u <= 0 or u >= 1:
    
25.         return False
    
26.     v = (dot00 * dot12 - dot01 * dot02) * div
    
27.     if v <= 0 or v >= 1:
    
28.         return False
    
29.     return u + v < 1
    
30. def euler102():
    
31.     count = 0
    
32.     with open('p102_triangles.txt') as file:
    
33.         for line in file:
    
34.             tmp = line.replace('\n', '').split(',')
    
35.             A = Vector2((int(tmp[0]), int(tmp[1])))
    
36.             B = Vector2((int(tmp[2]), int(tmp[3])))
    
37.             C = Vector2((int(tmp[4]), int(tmp[5])))
    
38.             if isInTri(A, B, C):
    
39.                 print(tmp)
    
40.                 count += 1
    
41.     print(count)
    
42. if __name__ == '__main__':
    
43.     start = time()
    
44.     euler102()
    
45.     print('cost %.6f sec' % (time() - start))

复制代码

debuggerzh

异端方法

                               
登录/注册后可看大图

guosl

利用内积的性质。

1. /*
   
2. 答案：228
   
3. */
   
4. #include <cstdio>
   
5. 
   
6. int main(void)
   
7. {
   
8.   errno_t err;
   
9.   FILE *fp = NULL;
   
10.   err = fopen_s(&fp, "p102_triangles.txt", "r");//打开文件
    
11.   if (err != 0)
    
12.   {
    
13.     printf_s("数据文件未打开\n");
    
14.     return 0;
    
15.   }
    
16.   int x[3], y[3];
    
17.   int nCount = 0;
    
18.   while (fscanf_s(fp, "%d,%d,%d,%d,%d,%d", &x[0], &y[0], &x[1], &y[1], &x[2], &y[2]) != EOF)
    
19.   {
    
20.     int d1 = x[0] * y[1] - x[1] * y[0];
    
21.     int d2 = x[1] * y[2] - x[2] * y[1];
    
22.     int d3= x[2] * y[0] - x[0] * y[2];
    
23.     if (d1 > 0 && d2 > 0 && d3 > 0 || d1 < 0 && d2 < 0 && d3 < 0)
    
24.       ++nCount;
    
25.   }
    
26.   fclose(fp);
    
27.   printf_s("%d\n", nCount);
    
28.   return 0;
    
29. }

复制代码