昨天的
还真的要求广义梯形的数量
原本想说就照原本想法 用 y=ax+b的a跟b当key去建hash table
不过WA
后来才想到，如果有平行四边形存在的话，这个平行四边形会被重复计算到
所以问题就变成，怎么找平行四边形
就整个变很复杂==
初步的想法是
两个线段，斜率相同，落在截距不同的直线上，且长度相同
这两个线段(四个点)组起来就会是平行四边形
用这个思路去硬干
就变成下面这样了
不过就 还是WA==
我受不了跑去问gemini
结果是精度问题 对ㄚ
就加个round就可以了 10是随便取的
def countTrapezoids(self, points: List[List[int]]) -> int:
PRECISION = 10
def find_line_params(point1, point2):
x1, y1 = point1
x2, y2 = point2
if x1 == x2:
return x1, None
a = (y2 - y1) / (x2 - x1)
b = y1 - a * x1
return round(a, PRECISION), round(b, PRECISION)
def calculate_distance(point1, point2):
x1, y1 = point1
x2, y2 = point2
delta_x = x2 - x1
delta_y = y2 - y1
distance = delta_x**2 + delta_y**2
return distance
n = len(points)
cnt = defaultdict(dict)
cnt_vertical = defaultdict(dict)
cnt_d_bya = defaultdict(dict)
cnt_d_vertical = defaultdict(int)
# count
for i in range(n):
for j in range(i+1, n):
a, b = find_line_params(points[i], points[j])
d = calculate_distance(points[i], points[j])
if d in cnt_d_bya[a]:
cnt_d_bya[a][d] += 1
else:
cnt_d_bya[a][d] = 1
if b is not None:
if b in cnt[a] and d in cnt[a][b]:
cnt[a][b][d] += 1
elif b in cnt[a]:
cnt[a][b][d] = 1
else:
cnt[a][b] = {d:1}
else:
cnt_d_vertical[d] += 1
if d in cnt_vertical[a]:
cnt_vertical[a][d] += 1
else:
cnt_vertical[a][d] = 1
# calc
rets = 0
n_parallel = 0 # number of parallelogram
for a, v in cnt.items():
s = 0
for b, v2 in v.items():
for d, n in v2.items():
s += n
n_parallel += ((cnt_d_bya[a][d]-n)*n)
for b, v2 in v.items():
s_b = 0
for d, n in v2.items():
s_b += n
rets += ((s-s_b)*s_b)
s = 0
for a, v in cnt_vertical.items():
for d, n in v.items():
s += n
n_parallel += ((cnt_d_vertical[d]-n)*n)
for a, v in cnt_vertical.items():
s_2 = 0
for d, n in v.items():
s_2 += n
rets += ((s-s_2)*s_2)
return rets//2-n_parallel//4