Skip to content

Instantly share code, notes, and snippets.

@NewFuture
Last active August 27, 2017 09:42
Show Gist options
  • Save NewFuture/bb90ecebfe39194a08e2f63bb41a82a9 to your computer and use it in GitHub Desktop.
Save NewFuture/bb90ecebfe39194a08e2f63bb41a82a9 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
import collections
def get_isosceles_trapezoid_num(edges):
d={}
sorted(edges)
for edge in edges:
d[edge] = d.get(edge,0) + 1
#字典排序
d = collections.OrderedDict(sorted(d.items()))
#腰至少存在两个
waist , edges = {k: v for k, v in d.items() if v>1}, list(d.keys())
length = len(edges)
total = 0
for w,n in waist.items():
times = n*(n-1)/2
# 有序遍历所有边
for i in range(0,length):
edge1 = edges[i]
num1 = d[edge1]
if edge1 == w:
if num1 > 2:
# 三个边相等
num1 = (n-2)/3
else:
continue
# 遍历最长边
for j in range(i+1,length):
edge2 = edges[j]
num2 = d[edge2]
if edge1 + w + w <= edge2:
#最长边大于其他三个边之和
break
if edge2 == w:
num2 = (n-2)/3
total += times*num1*num2
return int(total)
if __name__ == "__main__":
testcases = int(input())
for caseNr in range(1, testcases+1):
n=input()
data = [int(i) for i in input().split()]
print("Case #%i: %s" % (caseNr, get_isosceles_trapezoid_num(data)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment