我好后悔没有早点来看DJ宝的文
我刚刚debug 到很崩溃
已经查到-82.3333 不等于-82.3333了
想上来靠杯就看到这篇
我真的干你娘C++
我也要round了
※ 引述《DJYOMIYAHINA (通通打死)》之铭言：
: 昨天的
: 还真的要求广义梯形的数量
: 原本想说就照原本想法 用 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

c++ 哈哈

又差1 我真的要中风