昨天的
還真的要求廣義梯形的數量
原本想說就照原本想法 用 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