题解 | 三角谜题

根据其他同学的提示和启发，修改了寻找三条边的判断逻辑。

但是仍然存在两个问题：

1.提交不通过，使用自测数据和C++版的比对，结果是一样的，怀疑可能是系统问题。

2.因为第一条的原因，使用input()逐行读取是否会导致超时的问题也无法验证。我看C++版的好像也是逐行读取，运行也很快。（题目特意提醒了较快的读取方式，我试了一下sys.stdin，但是没有成功。）

末尾附上自测数据的生成方法。

代码仅供参考，欢迎后面的同学指正。

import math
from collections import defaultdict


def calculate_area(a, b):   # 腰，底
    # 使用海伦公式计算三角形面积: s = (a + b + c) / 2
    # math.sqrt(s * (s - a) * (s - b) * (s - c))
    area = math.sqrt(a ** 2 - b ** 2 / 4) * b / 2   # c = a，化简一下公式
    return round(area, 10)


def solve(num):     # num是降序的
    lst1 = []   # 数量为1的棍子，降序
    lst2 = []   # 数量大于等于2的棍子，降序
    for each in num:
        if each[1] >= 2:
            lst2.append(each)
        else:
            lst1.append(each)
    if not lst2:    # lst2为空，不存在等腰三角形
        return 0, 0
    if lst2[0][1] >= 3:
        return lst2[0][0], lst2[0][0]   # 腰，底
    else:   # 寻找底边
        if len(lst2) == 1:  # lst2只有1种棍子
            if not lst1:        # lst1为空
                return 0, 0
            while lst1:        # lst1不为空，底边来自lst1，遍历lst1，判断是否构成三角形
                if lst2[0][0] * 2 > lst1[0][0]:
                    return lst2[0][0], lst1[0][0]
                lst1.pop(0)     # 弹出lst1第一个元素
            return 0, 0     # lst1中找不到可以构成三角形的
        else:       # lst2至少有2种棍子
            if not lst1:    # lst1为空，底边来自lst2，且必然能构成三角形
                return lst2[0][0], lst2[1][0]
            else:   # lst1不为空，底边可能来自lst1或lst2，如果来自lst1，要判断是否构成三角形
                db1 = lst2[1][0]
                db2 = 0
                while lst1:  # lst1不为空，底边来自lst1，遍历lst1，判断是否构成三角形
                    if lst2[0][0] * 2 > lst1[0][0]:
                        db2 = lst1[0][0]
                        break
                    lst1.pop(0)  # 弹出lst1第一个元素
                return lst2[0][0], max(db1, db2)


while True:
    try:
        T = int(input())
        res = []
        for _ in range(T):
            n = int(input())
            temp = defaultdict(int)     # defaultdict() 生成一个带默认值的字典
            # 如果要查找的键不在字典中，不会抛出异常，而是会调用括号内的函数生成一个默认值
            for _ in range(n):
                length, cnt = map(int, input().split())
                temp[length] += cnt
            lst = sorted(temp.items(), key=lambda x: x[0], reverse=True)
            res.append(lst)
        for i in res:
            a, b = solve(i)
            if a != 0:
                print(calculate_area(a, b))
            else:
                print(-1)
    except:
        break

# 生成测试数据
import random

with open('D:\Document\HJ112_data.txt', 'w') as f:      # 路径改成自己的本地路径
    T = random.randint(10, 20)
    f.write(f'{T}\n')
    for _ in range(T):
        n = random.randint(1, 500)
        f.write(f'{n}\n')
        for _ in range(n):
            l = random.randint(1, 500)
            a = random.randint(1, 500)
            f.write(f'{l} {a}\n')