【py交易】算法竞赛入门经典5.4.3果园里的树 Python

分析：
1.可借助三角形的有向面积计算，原理不懂，但是有公式，记住就可：

如果 》0，则说明ABC三点呈现逆时针排列，<0反之，=0共线
2.三个点为A、B、C，三个点的x最大值是maxX，最小值是minX，y最大值是maxY，最小值是minY，虽然x和y属于1到99，但是x只需要遍历minX到maxX，y只需要遍历minY到maxY的整数点就可以了
3.假设任意一个点为P，则三角形内的树的位置p应满足Sabc>=Spab+Spac+Spbc
4. if abs((Spab + Spbc + Spac) - Sabc) < eps 这句最开始是if (Spab + Spbc + Spac)<=Sabc,但算出来不对，dont knw why。。。以后再研究py的浮点数问题（flag）
5.py居然没有三目运算符！
6.输入 1.5 1.5 1.5，6.8 6.8，1.5这种输入格式暂不知道如何用py实现（摊手，whatever）

# coding=utf-8import  math
"5.4.3果园里的树""输入三个点，求出三个点所围成的三角形的有向面积"
def triangleArea(x1,y1,x2,y2,x3,y3):area = ( x1*y2 + x3*y1 + x2*y3 - x3*y2 - x1*y3 - x2*y1)/2if area < 0:area = -areareturn  areaa = raw_input()
x1 = float(a.split(",")[0])
y1 = float(a.split(",")[1])
b = raw_input()
x2 = float(b.split(",")[0])
y2 = float(b.split(",")[1])
c = raw_input()
x3 = float(c.split(",")[0])
y3 = float(c.split(",")[1])Sabc  = triangleArea(x1,y1,x2,y2,x3,y3)# print "Sabc = ",Sabc
"找出x和y的上下界，减少遍历的次数"
"下界1.5时，应该为2，上取整"
"上届6.8时，应该为6，下取整"
minX = int(math.ceil(min(x1,x2,x3)))
maxX = int(max(x1,x2,x3))
minY = int(math.ceil(min(y1,y2,y3)))
maxY = int(max(y1,y2,y3))potNum = 0
eps = 0.0001#误差，xjb选的
for i in range(minX,maxX+1,1):for j in range(minY,maxY+1,1):# print i,jSpab = triangleArea(i,j,x1,y1,x2,y2)Spac = triangleArea(i,j,x1,y1,x3,y3)Spbc = triangleArea(i,j,x2,y2,x3,y3)if abs((Spab + Spbc + Spac) - Sabc) < eps :# print (Spab + Spbc + Spac)potNum += 1# print Spab,Spac,Spbc
print potNum

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！