每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数,每组测试数据描述如下:
第一行输入一个整数
代表棍子的种类。
此后
行,第
行输入两个整数
代表第
种棍子的长度和数量。
除此之外,保证单个测试文件的
之和不超过
。
在一行上输出一个实数,代表组成的最大等腰三角形的面积。如果无法组成等腰三角形,则直接输出
。
由于实数的计算存在误差,当误差的量级不超过
时,您的答案都将被接受。具体来说,设您的答案为
,标准答案为
,当且仅当
时,您的答案将被接受。
2 3 3 3 2 1 3 1 2 1 2 12 1
3.89711431702997391060 -1
对于第一组测试数据,可以构造
为底、
为腰的三角形,面积
;也可以构造
为底、
为腰的三角形,面积
。显然,后者更大。
本题数据量较大,我们建议您使用较快的读入方式。
#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; }
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)
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)); }
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) } } }
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)
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; } }
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); } }