首页 > 试题广场 >

三角谜题

[编程题]三角谜题
  • 热度指数:3417 时间限制: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}本题数据量较大,我们建议您使用较快的读入方式。
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)