三角形内格点数量:皮克定理
from operator import abs
def renj(pts):
X=[]
Y=[]
for i in range(len(pts)):
if i in [0,2,4]:
X.append(pts[i])
else:
Y.append(pts[i])
return [min(X), max(X), min(Y), max(Y)]
def m(a,b):
from math import e
if b[0]-a[0]:
return (b[1]-a[1])/(b[0]-a[0])
return e
def test(a,b,z):
if m(a,b)==m(a,z):
return 1
return 0
n=int(input())
for i in range(n):
points = list(map(int, input().split()))
count = 0
A=[points[0], points[1]]
B=[points[2], points[3]]
C=[points[4], points[5]]
r = renj(points)
for u in range(r[0], r[1]+1):
for v in range(r[2], r[3]+1):
Z=[u, v]
if test(A,B,Z) or test(A,C,Z) or test(B, C, Z):
count += 1
aa=abs((A[0]*(B[1]-C[1])+B[0]*(C[1]-A[1])+C[0]*(A[1]-B[1]))/2)
bb=count
ii=(aa+1)-bb/2
print(int(ii))
该解决方案基于:皮克定理
A + 1 = i + b/2
A:三角形的面积
i:内部点数
b:边界点数,包括顶点
注意:仅适用于整数点。欢迎社区提出建议。
![enter image description here](https://istack.dev59.com/Ba5TQ.webp)
代码片段
输入 用于整数输入。
1
2 4 8 2 10 6
输出
12 # 因为三角形中有12个点