计算构成三角形的个数

题目描述

二维平面直角坐标系中有N个整形坐标点(x1,y1),(x2,y2),..(xN,yN),任意三个点都可能构成一个三角形，计算构成三角形的个数。

输入描述

输入有两行：
第一行为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 defaultdict
from 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))

作者：​​楚千羽​​