小练习 20170508 文件中的三角形中有多少个内部包含原点？

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即5.8 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释


一些鱼油反映题目有些过难，为此略过一部分偏难的题目。


题目：

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

考虑如下两个三角形：

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

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

可以证明三角形 ABC 包含原点在其内部，而三角形 XYZ 则不包含。
附件文件（请将后缀rar改为txt） 包含一千个随机三角形，求其中有多少个三角形的内部包含原点。

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

WelanceLee

1. def product(a, b):
   
2.     return a[0]*b[0] + a[1]*b[1]
   
3. 
   
4. def sign(x, y, z):
   
5.     if x < 0 and y < 0 and z < 0:
   
6.         return True
   
7.     elif x > 0 and y < 0 and z < 0:
   
8.         return True
   
9.     elif y > 0 and x < 0 and z < 0:
   
10.         return True
    
11.     elif z > 0 and x < 0 and y < 0:
    
12.         return True
    
13.     else:
    
14.         return False
    
15.    
    
16. with open('p102_triangles.txt') as f:
    
17.     content = f.readlines()
    
18. for i in range(len(content)):
    
19.     content[i] = content[i].rstrip().split(',')
    
20.     content[i] = list(map(float, content[i]))
    
21. 
    
22. i = 0
    
23. for each in content[:1]:
    
24.     a = [each[0], each[1]]
    
25.     b = [each[2], each[3]]
    
26.     c = [each[4], each[5]]
    
27.     if sign(product(a, b),product(b, c), product(a, c)):
    
28.         i += 1
    
29. 
    
30. print(i)

复制代码

答案是598

ooxx7788

1. import pandas as pd
   
2. # from mytoolbox.myusetime import usetime
   
3. 
   
4. # @usetime
   
5. def main():
   
6.     df = pd.read_table(r'C:\Users\letian\Desktop\python\p102_triangles.txt', sep=',',
   
7.                        names=['x1', 'y1', 'x2', 'y2', 'x3', 'y3'])
   
8.     df['x0'] = 0
   
9.     df['y0'] = 0
   
10.     df['S'] = abs(((df['x2'] - df['x1']) * (df['y3'] - df['y1']) - (df['y2'] - df['y1']) * (df['x3'] - df['x1'])) / 2)
    
11.     df['S1'] = abs(
    
12.         ((df['x2'] - df['x0']) * (df['y3'] - df['y0']) - (df['y2'] - df['y0']) * (df['x3'] - df['x0'])) / 2) + abs(
    
13.         ((df['x2'] - df['x1']) * (df['y0'] - df['y1']) - (df['y2'] - df['y1']) * (df['x0'] - df['x1'])) / 2) + abs(
    
14.         ((df['x0'] - df['x1']) * (df['y3'] - df['y1']) - (df['y0'] - df['y1']) * (df['x3'] - df['x1'])) / 2)
    
15.     return (df['S'] - df['S1']).value_counts(0)[0.0]
    
16. 
    
17. 
    
18. if __name__ == '__main__':
    
19.     print(main())

复制代码

我就搞点这种没有技术含量的吧，向量计算面积。实线区域面积等于虚线面积者为点在三角形内。
不过这种读取文件的题目，对计算时间的影响应该比较大吧。

1. Total used 0.013002s, loops: 1.
   
2. 228

复制代码

jerryxjr1220

第一种方法是同向法，假设点P位于三角形内，会有这样一个规律，当我们沿着ABCA的方向在三条边上行走时，你会发现点P始终位于边AB，BC和CA的右侧。我们就利用这一点，但是如何判断一个点在线段的左侧还是右侧呢？我们可以从另一个角度来思考，当选定线段AB时，点C位于AB的右侧，同理选定BC时，点A位于BC的右侧，最后选定CA时，点B位于CA的右侧，所以当选择某一条边时，我们只需验证点P与该边所对的点在同一侧即可。问题又来了，如何判断两个点在某条线段的同一侧呢？可以通过叉积来实现，连接PA，将PA和AB做叉积，再将CA和AB做叉积，如果两个叉积的结果方向一致，那么两个点在同一测。判断两个向量的是否同向可以用点积实现，如果点积大于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)

复制代码

另一种比较好的方法是比较顶点到原点构成的三角形面积之和，如果原点在三角形内部则面积之和应该想等，不然就不相等。

1. def sq(a, b, c):
   
2.     A = ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5
   
3.     B = ((b[0] - c[0])**2 + (b[1] - c[1])**2)**0.5
   
4.     C = ((c[0] - a[0])**2 + (c[1] - a[1])**2)**0.5
   
5.     P = (A + B + C) / 2
   
6.     return (P * (P - A) * (P - B) * (P - C))**0.5
   
7.    
   
8. with open('p102_triangles.txt') as f:
   
9.     lines = f.readlines()
   
10.    
    
11. count = 0
    
12. for line in lines:
    
13.     lst = line.split(',')
    
14.     a = (int(lst[0]), int(lst[1]))
    
15.     b = (int(lst[2]), int(lst[3]))
    
16.     c = (int(lst[4]), int(lst[5]))
    
17.     o = (0, 0)
    
18.     s1 = sq(a, b, o)
    
19.     s2 = sq(b, c, o)
    
20.     s3 = sq(c, a, o)
    
21.     s = sq(a, b, c)
    
22.     if s1 + s2 + s3 - s < 0.0001:
    
23.         count  += 1
    
24. print(count)

复制代码

输出：
228

余欲渔

我这题做的有点漏洞

1. def sj(j):
   
2.     ax,ay,bx,by,cx,cy=j[0],j[1],j[2],j[3],j[4],j[5]
   
3.     if ax-bx==0 and ax*cx>0 or bx-cx==0 and ax*bx>0 or ax-cx==0 and ax*bx>0:
   
4.         return 0
   
5.     elif ax-bx==0 and ax*cx<0 or bx-cx==0 and ax*bx<0 or ax-cx==0 and ax*bx<0:
   
6.         return 1
   
7.     k1=(ay-by)/(ax-bx)
   
8.     b1=ay-ax*k1
   
9.     k2=(by-cy)/(bx-cx)
   
10.     b2=by-bx*k2
    
11.     k3=(cy-ay)/(cx-ax)
    
12.     b3=cy-cx*k3
    
13.     fa=lambda x,y:k1*x+b1-y
    
14.     fb=lambda x,y:k2*x+b2-y
    
15.     fc=lambda x,y:k3*x+b3-y
    
16.     if fa(0,0)*fa(cx,cy)>0 and fb(0,0)*fb(ax,ay)>0 and fc(0,0)*fc(bx,by)>0:return 1
    
17.     return 0
    
18. F=open(r'G:\pyc\p102_triangles.txt')
    
19. js=0
    
20. for i in F:
    
21.     if sj([int(j) for j in i.split(',')]):
    
22.         js+=1
    
23. F.close()
    
24. print(js)

复制代码

1. RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
   
2. 228
   
3. >>>

复制代码

小剑剑

1. f=open('p102_triangles.txt','r')
   
2. s=f.read().split('\n')[:-1]
   
3. point=[]
   
4. for  i in s:
   
5.        point.append(tuple(map(int,i.split(','))))
   
6. 
   
7. def func(tu,inde):
   
8.        a=[0,2,4]
   
9.        one=a.pop(inde)
   
10.        lip1=a.pop()
    
11.        lip2=a.pop()
    
12.        x1,y1=tu[lip1],tu[lip1+1]
    
13.        x2,y2=tu[lip2],tu[lip2+1]
    
14.        x3,y3=tu[one],tu[one+1]
    
15.        del one ,lip1,lip2,a
    
16.        if x1==x2:
    
17.               if x1==0:
    
18.                      return y2*y1<0
    
19.               return x1*(x1-x3)>0
    
20.        if x1>x2:
    
21.               x1,y1,x2,y2=x2,y2,x1,y1
    
22.        a=(y1-y3)*(x2-x1)+(y1-y2)*(x1-x3)
    
23.        b=y1*(x2-x1)-(y2-y1)*x1
    
24.        if a>0 and b>0:
    
25.               return True
    
26.        if a<0 and b<0:
    
27.               return True
    
28.        return False
    
29. 
    
30. ti=1000
    
31. for i in point:
    
32.        for ii in range(3):
    
33.               if not func(i,ii):
    
34.                      ti-=1
    
35.                      break

复制代码

228

我是o记

228

1. file=open('p102_triangles.txt','r')
   
2. points=[]
   
3. for i in file.read().split('\n')[:-1]:
   
4.        points.append(tuple(map(int,i.split(','))))
   
5. file.close()
   
6. def judge(tu,inde):
   
7.        num=[0,2,4]
   
8.        fir=num.pop(inde)
   
9.        li1,li2=num[0],num[1]
   
10.        x1,y1=tu[li1],tu[li1+1]
    
11.        x2,y2=tu[li2],tu[li2+1]
    
12.        x3,y3=tu[fir],tu[fir+1]
    
13.        if x1>x2:
    
14.               x1,y1,x2,y2=x2,y2,x1,y1
    
15.        try:
    
16.               b3=y3-y1+(y2-y1)/(x2-x1)*(x1-x3)
    
17.        except ZeroDivisionError:
    
18.               if x2==0:
    
19.                      return y2*y1<0
    
20.               return x2*(x2-x3)>0
    
21.        #print(x1,y1,x2,y2,x3,y3)
    
22.        b1=y1-(y2-y1)/(x2-x1)*x1
    
23.        r1=b3>0
    
24.        r2=b1>0
    
25.        if r1==r2:
    
26.               return False
    
27.        return True
    
28. 
    
29. count=0
    
30. for i in points:
    
31.        flag=1
    
32.        for ii in range(3):
    
33.               if not judge(i,ii):
    
34.                      flag=0
    
35.                      break
    
36.        if flag:
    
37.               count+=1

复制代码

lovesword

没有看到 除了网上的面积法 和 向量法的 第三种解决办法 有点失望。。。

冬雪雪冬

lovesword 发表于 2017-5-17 11:07
没有看到 除了网上的面积法 和 向量法的 第三种解决办法 有点失望。。。

我的思路：
1.计算角度，从原点到三角形的顶点引三条线形成的三个不大于180度的夹角，夹角之和为360度，则原点在三角形之内。
2.三角形三边如果与x轴y轴相交，且相交点分别在0点两边或只有一个相交点在0点，则为True