首页 > 试题广场 >

三角谜题

[编程题]三角谜题
  • 热度指数:3368 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 n 种长度的棍子,第 i 种棍子的长度为 l_i ,有 a_i 根。从中任选三根,能组成的等腰三角形的面积最大值为多少?
\hspace{15pt}如果无法组成等腰三角形,则直接输出 -1

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^6 \right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n \left( 1\leqq n \leqq 10^6 \right) 代表棍子的种类。
\hspace{15pt}此后 n 行,第 i 行输入两个整数 l_i, a_i \left(1 \leqq l_i, a_i \leqq 10^9 \right) 代表第 i 种棍子的长度和数量。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 10^6


输出描述:
\hspace{15pt}在一行上输出一个实数,代表组成的最大等腰三角形的面积。如果无法组成等腰三角形,则直接输出 -1

\hspace{15pt}由于实数的计算存在误差,当误差的量级不超过 10^{-6} 时,您的答案都将被接受。具体来说,设您的答案为 a ,标准答案为 b ,当且仅当 \frac{|a-b|}{\max(1,|b|)}\leqq 10^{-6} 时,您的答案将被接受。
示例1

输入

2
3
3 3
2 1
3 1
2
1 2
12 1

输出

3.89711431702997391060
-1

说明

\hspace{15pt}对于第一组测试数据,可以构造 2 为底、3 为腰的三角形,面积 \approx 2.83 ;也可以构造 3 为底、3 为腰的三角形,面积 \approx 3.90 。显然,后者更大。

备注:
\hspace{15pt}本题数据量较大,我们建议您使用较快的读入方式。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main() {
    long long T;
    scanf("%lld",&T);
    long long n;  
    while(scanf("%lld", &n) != EOF){ 
    long long l[1000000],a[1000000];
    long long i,j,k;
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld\n",&l[i],&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(l[j] == l[i]) 
            {
                a[i] += a[j];
                n--;
                for(k=j;k<=n;k++)
                {
                    a[k] = a[k+1];
                    l[k] = l[k+1];
                }
            }
        }
    }
    int temp1,temp2;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n-i;j++)
        {
            if(l[j] < l[j+1]) 
            {
                temp1 = l[j+1];
                l[j+1] = l[j];
                l[j] = temp1;
                temp2 = a[j+1];
                a[j+1] = a[j];
                a[j] = temp2;
            }
        }
    }
    long long x,y,z;
    int flag = 0;
    double c;
    double s;
    for(i=1;i<=n;i++)
    {
        if(a[i] > 2)
        {
            x = l[i];
            y = l[i];
            for(j=1;j<=i;j++)
            {
                if(l[j] < (x+y))
                {
                    z = l[j];
                    flag = 1;
                    break;
                }
            }
            break;
        }
        else if(a[i] == 2)
        {
            x = l[i];
            y = l[i];
            for(j=1;j<=n;j++)
            {
                if(l[j] < (x+y) && l[j] != l[i])
                {
                    z = l[j];
                    flag = 1;
                    break;
                }
            }
            break;
        }
    }
    if(flag == 0) printf("-1\n");
    else
    {
        c = (long double)(z + 2*x)/2;
        s = (long double)sqrt(c * (c-z) * (c-x) * (c-x));
        printf("%.10lf\n",s);
    }
    }
    return 0;
}

发表于 2025-07-19 10:19:18 回复(0)
海伦公式计算,暴力求解,只能跑到第四个用例
import sys
import math

T = int(input())

def cal_area(a: int, c: int):
    s = float((a + a + c) / 2)
    return math.sqrt(s * (s - a) * (s - a) * (s - c))

for _ in range(T):
    n = int(input())
    datas = {}
    for _ in range(n):
        l, a = map(int, input().split(' '))
        if l in datas:
            datas[l] += a
        else:
            datas[l] = a
    
    bians = sorted(datas, reverse=True)

    max_area = -1
    for i, a in enumerate(bians):
        n_a = datas[a]

        if n_a >= 2:
            if n_a >= 3:
                cs = bians
            else:
                cs = bians[:i] + bians[i+1:]

            c = None
            for c_ in cs:
                if 2 * a > c_:
                    max_area = max(cal_area(a, c_), max_area)
        else:
            continue
    print(max_area)




发表于 2025-07-04 21:34:57 回复(0)
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
let t, arr = [], index = 0;
rl.on('line', (line) => {
    if (t === undefined) {
        t = Number(line);
        arr = new Array(t);
    } else {
        if (!arr[index]) {
            arr[index] = [Number(line)]
        } else {
            if (arr[index].length < arr[index][0] + 1) {
                arr[index].push(line);
            }
            if (arr[index].length === arr[index][0] + 1) {
                index++;
                if (index === t) {
                    rl.close();
                }
            }
        }
    }
    
})
rl.on('close', () => {
    arr.forEach(item => {
        helper(item.slice(1));
    })
})
// 等腰三角形面积计算,p=a+b/2, s = (p-a)*sqrt(p*(p-b)); 
// 从上面的计算公式可以算出, 对面积影响最大的是b,至于a越大越好, 并且 b < 2a
function helper(list) {
    let ll = [];
    let a = 0; // 腰长
    for(let i=0; i<list.length; i++) {
        const tokens = list[i].split(' ');
        const l = Number(tokens[0]);
        const count = Number(tokens[1]);
        if (count >= 2 && l > a) {
            a = l;
        }
        ll.push([l, count]);
    }
    // console.log('腰长', a, ll);
    let b = 0; // 底长
    let max = -1;
    if (a === 0) {
        console.log(max);
        return;
    }
    for(let i=0; i<ll.length; i++) {
        if (
            ((ll[i][0] === a && ll[i][1] >= 3) || (ll[i][0] != a && ll[i][1] >= 1))
            && ll[i][0] < 2 * a
        ) {
            // console.log('找到合适的底', ll[i][0]);
            let s = calc_area(a, ll[i][0]);
            if (s > max) {
                max = s;
                b = ll[i][0];
            }
        }
    }
    console.log(max);
}
function calc_area(a, b) {
    const p = parseFloat((2 * a + b) / 2);
    return (p-a) * Math.sqrt(p * (p-b));
}
这里是不是精度异常导致的, 题目是否可以求找到最大面积的腰长和底长
发表于 2025-06-04 22:04:28 回复(0)
package main

import (
	"fmt"
    "math"
    "sort"
)

func CalulateIsosceLestriangleSpare(LenIso float64, LenDown float64) float64 {
	//fmt.Println(LenIso, LenDown)
	h := math.Sqrt(LenIso*LenIso - LenDown/2.0*LenDown/2.0)
	return h * LenDown / 2.0
}

func IsConstructTriangle(LenIso float64, LenDown float64) bool {
	if LenIso*2.0 > LenDown {
		return true
	}
	return false
}

func SortAndDelCopyer(PIAArr [][]float64) [][]float64 {
	DCDict := make(map[float64]float64)
	for _, v := range PIAArr {
		item, err := DCDict[v[0]]
		if err {
			DCDict[v[0]] = item + v[1]
		} else {
			DCDict[v[0]] = v[1]
		}
	}
	var PIA [][]float64
	for v := range DCDict {
		PIA = append(PIA, []float64{v, DCDict[v]})
	}
	PIAArr = PIA
	sort.Slice(PIAArr, func(i, j int) bool {
		return PIAArr[i][0] > PIAArr[j][0]
	})
	//fmt.Println("SortAndDelCopyer", PIAArr)
	return PIAArr
}

func main() {
	var num int
	var HandleArr [][][]float64
	fmt.Scan(&num)
	for i := 0; i < num; i++ {
		var itemnum int
		fmt.Scan(&itemnum)
		var item [][]float64
		for j := 0; j < itemnum; j++ {
			var lenger, number float64
			fmt.Scanf("%f %f", &lenger, &number)
			item = append(item, []float64{lenger, number})
		}
		HandleArr = append(HandleArr, item)
	}
	flag := 0
	for _, v := range HandleArr {
		v = SortAndDelCopyer(v)
		//fmt.Println(v)
		flag = 0
		for i := 0; i < len(v); i++ {
			if v[i][1] >= 3 {
				flag = 1
				fmt.Printf("%.10f\n", CalulateIsosceLestriangleSpare(v[i][0], v[i][0]))
				break
			} else if v[i][1] == 2 {
				for j := i - 1; j >= 0; j-- {
					if IsConstructTriangle(v[i][0], v[j][0]) {
						fmt.Printf("%.10f\n", CalulateIsosceLestriangleSpare(v[i][0], v[j][0]))
						flag = 1
						break
					}
				}
				if flag == 1 {
					break
				}
				if i != len(v)-1 {
					if IsConstructTriangle(v[i][0], v[i+1][0]) {
						fmt.Printf("%.10f\n",CalulateIsosceLestriangleSpare(v[i][0], v[i+1][0]))
						flag = 1
						break
					}
				}
				if flag == 1 {
					break
				}
				continue
			}
		}
		if flag == 0 {
			fmt.Println(-1)
		}
	}
}

发表于 2025-05-28 13:11:55 回复(0)
答案应该是对的,但是提交超时通不过,可以参考我的写法,
from collections import defaultdict
import math
T = input() # 组数
for _ in range(int(T)):
    n = input()
    t = defaultdict(int)  # 字典保存每组不同长度的棍子及其数量
    for i in range(int(n)):
        s = input().split()
        t[int(s[0])] += int(s[1])
    area = -1  # 面积,初始为-1
    for x in t:
        if t[x] >= 2: # 遍历字典,取两根相同长度的棍子,
            t[x] -= 2 # 取两根棍子,数量减2
            a = x # a为三角形的腰
            for y in t:
                if 0 < y < a*2 and t[y] > 0:
                    b = y # b为三角形的底边
                    area = max(area, math.sqrt(a**2-(b/2)**2)*b/2) # 计算面积
            t[x] += 2 # 棍子用完之后要加回来
    print(area)


发表于 2025-04-25 01:41:16 回复(1)
为什么不能通过,明明代码是正确的

import math
def cal(arr1,arr2):
    arr=[]
    #print(arr1,arr2)
    for i,j in zip(arr1,arr2):
        arr.append([i,j])
    arr.sort(reverse=True)
    area=-1
    for i in range(len(arr)):
        if arr[i][1]>=2:
            y=arr[i][0]
            arrx=[]
            if i>=1:
                x=arr[i-1][0]
                if x<2*y:
                    arrx.append(x)
            if arr[i][1]>2:
                arrx.append(arr[i][0])
            if i+1<len(arr):
                arrx.append(arr[i+1][0])
            for x in arrx:
                h2=y**2-(x/2)**2
                #temp= math.sqrt((h2/4)*((x)**2))
                s = (y+y+x) / 2
                temp=math.sqrt(s * (s - y) * (s - y) * (s - x))
                #temp=h*x/2
                if area<temp:
                    area=temp
            if area>-1:  
                    return area
    return -1
while True:
    try:
        n=int(input())
        for _ in range(n):
            k=int(input())
            arr1,arr2=[],[]
            for i in range(k):
                l,a=list(map(int,input().split()))
                if l in arr1:
                    idx=arr1.index(l)
                    arr2[idx]=arr2[idx]+a
                else:
                    arr1.append(l)
                    arr2.append(a)
            res=cal(arr1,arr2)
            print(res)

    except:
        break
发表于 2025-04-09 17:50:09 回复(0)
解题思路:
1. 按照长度逆序排序,key:木棍长度,value:数量
2. 遍历value集合,找到第一个数量大于1的木棍 i 作为腰
3. 从0开始遍历key,一直到第二步的 i+1 个,找到第一个符合等腰三角形的组合,就是最大值
代码参考如下:(Math.sqrt方法精度只能到15或16,本题精确到了20,于是自定义了sqrt方法)
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int total = in.nextInt();
        BigDecimal[] result = new BigDecimal[total];
        for (int i = 0; i < total; i++) {
            int typeCount = in.nextInt();
            int[][] lenAndNum = new int[typeCount][2];
            for (int j = 0; j < typeCount; j++) {
                lenAndNum[j][0] = in.nextInt();
                lenAndNum[j][1] = in.nextInt();
            }
            result[i] = getResult(lenAndNum);
        }
        for (BigDecimal d : result) {
            System.out.println(d);
        }
    }

    public static BigDecimal getResult(int[][] lenAndNum) {
        Map<BigDecimal, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < lenAndNum.length; i++) {
            BigDecimal len  = BigDecimal.valueOf(lenAndNum[i][0]);
            int num = lenAndNum[i][1];
            if (map.containsKey(len)) {
                map.put(len, map.get(len) + num);
            } else {
                map.put(len, num);
            }
        }
        map = map.entrySet().stream().sorted(Collections.reverseOrder(
                Map.Entry.comparingByKey())).collect(
                  Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (l1, l2)->l1,
                                   LinkedHashMap::new));
        List<BigDecimal> keyList = new LinkedList<>();
        List<Integer> valueList = new LinkedList<>();
        for (Map.Entry<BigDecimal, Integer> item : map.entrySet()) {
            keyList.add(item.getKey());
            valueList.add(item.getValue());
        }
        for (int i = 0; i < valueList.size(); i++) {
            Integer num = valueList.get(i);
            if (num >= 2) {
                for (int j = 0; j < Math.min(i + 1, valueList.size()); j++) {
                    if (num > 2) {
                        BigDecimal result = cal(keyList.get(i), keyList.get(j));
                        if (result.compareTo(BigDecimal.ZERO) > 0) {
                            return result;
                        }
                    }
                    if (num == 2 && i != j) {
                        BigDecimal result = cal(keyList.get(i), keyList.get(j));
                        if (result.compareTo(BigDecimal.ZERO) > 0) {
                            return result;
                        }
                    }
                }
            }
        }
        return BigDecimal.valueOf(-1);
    }

    public static BigDecimal cal(BigDecimal yao, BigDecimal di) {
        if (yao.add(yao).compareTo(di) < 0) {
            return new BigDecimal(-1);
        }
        BigDecimal halfDi = di.divide(BigDecimal.valueOf(2), 20, RoundingMode.HALF_UP);
        BigDecimal sqrtValue = yao.multiply(yao).subtract(halfDi.multiply(
                                   halfDi));
        BigDecimal gao = sqrt(sqrtValue, 20);
        return di.multiply(gao).divide(BigDecimal.valueOf(2), 20,
                                       RoundingMode.HALF_UP);
    }

    public static BigDecimal sqrt(BigDecimal num, int precision) {
        // 负数不能开平方
        if (num.compareTo(BigDecimal.ZERO) < 0) {
            throw new ArithmeticException("不能对负数开平方");
        }
        MathContext context = new MathContext(precision, RoundingMode.HALF_UP);
        BigDecimal guess = num.divide(BigDecimal.valueOf(2), context);
        BigDecimal tolerance = BigDecimal.ONE.scaleByPowerOfTen(-precision);
        while (true) {
            BigDecimal nextGuess = guess.add(num.divide(guess,
                                             context)).divide(BigDecimal.valueOf(2), context);
            if (nextGuess.subtract(guess).abs().compareTo(tolerance) <= 0) {
                return nextGuess;
            }
            guess = nextGuess;
        }
    }


发表于 2025-03-22 16:24:10 回复(0)
遍历所有的底边和侧边,求最大面积即可。但不知道为啥超时了。
use std::collections::HashMap;
use std::io::*;

fn solve(group: HashMap<usize, usize>) {
    let congruent_group: HashMap<usize, usize> = group
        .iter()
        .filter(|(_, &v)| v >= 2)
        .map(|(k, v)| (*k, *v))
        .collect();
    if congruent_group.is_empty() {
        println!("-1");
        return;
    }
    let mut max_area = 0.0f64;
    let mut found = false;
    for base_side in group.iter() {
        let (&length_b, _) = base_side;
        for congruent_side in congruent_group.iter() {
            let (&length_c, &count_c) = congruent_side;
            if 2 * length_c <= length_b {
                continue;
            }
            if length_b != length_c && count_c < 2 {
                continue;
            }
            if length_b == length_c && count_c < 3 {
                continue;
            }
            found = true;
            let area = (length_b as f64)
                * (length_c.pow(2) as f64 - length_b.pow(2) as f64 / 4.0).sqrt()
                / 2.0;
            max_area = max_area.max(area);
        }
    }
    if found {
        println!("{}", max_area);
    } else {
        println!("-1");
    }
}
fn main() {
    let stdin = stdin();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    line.pop();
    let t: usize = line.parse().unwrap();
    for _ in 0..t {
        line.clear();
        stdin.read_line(&mut line).unwrap();
        line.pop();
        let n: usize = line.parse().unwrap();
        let lines: Vec<(usize, usize)> = stdin
            .lock()
            .lines()
            .take(n)
            .map(|l| {
                let l = l.unwrap();
                let mut it = l.split_whitespace();
                (
                    it.next().unwrap().parse().unwrap(),
                    it.next().unwrap().parse().unwrap(),
                )
            })
            .collect();
        let group = lines.iter().fold(HashMap::new(), |mut acc, &(a, b)| {
            acc.entry(a).and_modify(|x| *x += b).or_insert(b);
            acc
        });
        solve(group);
    }
}


发表于 2025-03-06 11:34:49 回复(0)