计算构成三角形的个数

计算构成三角形的个数

题目描述

输入描述

输入有两行： 第一行为N. 3 ≤ N ≤ 256 第二行为输入N个双字节整型坐标点，共2N个数据，以空格分隔横纵坐标及不同的点，x1,y1,x2,y2,...,xn,yn,xN,yN

输出描述

输出直角三角形的个数

示例1

输入输出示例仅供调试，后台判断数据一般不包含示例

输入

4 0 0 2 0 1 1 2 2

输出

3

输入

3 0 0 2 0 1 1

输出

1

题目分析

Python代码实现

from collections import defaultdictfrom math import gcd def countTriangles(P, N): mp = defaultdict(lambda:0) ans = 0 for i in range(0, N): mp.clear() for j in range(i + 1, N): X = P[i][0] - P[j][0] Y = P[i][1] - P[j][1] g = gcd(X, Y) X //= g Y //= g mp[(X, Y)] += 1 num = N - (i + 1) ans += (num * (num - 1)) // 2 for j in mp: ans -= (mp[j] * (mp[j] - 1)) // 2 return ans if __name__ == "__main__": N = int(input()) ls = list(map(int,input().strip().split())) P = [] for i in range(0,2*N,2): P.append([ls[i],ls[i+1]]) print(countTriangles(P, N))

作者：​​楚千羽​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。