Skip to Content
CTRL K

Rudolph and Christmas Tree

Editorial oficial (C++) 

Explicación

Procesamos las ramas de más baja a más alta, calculando para cada rama la cantidad de área que no queda cubierta por una posterior. Mirando la imagen del caso de ejemplo dado en el enunciado, estaríamos calculando el área delineada en negro para cada rama.

Para cada rama, hay dos casos:

  1. Ninguna rama cubre la actual. En este caso, sumamos dh2\frac{dh}{2} al total, ya que esa es la fórmula del área de un triángulo.
  2. Una rama cubre la actual, convirtiéndola en un trapecio. En este caso, hay que usar la fórmula del área de un trapecio, que es h(b1+b2)2\frac{h(b_1+b_2)}{2}, donde b1b_1 y b2b_2 son las longitudes de las bases superior e inferior.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
/** @return el área de un trapecio con las longitudes de base y la altura dadas */
double trap_area(double base1, double base2, double height) {
	return height * (base1 + base2) / 2;
}
 
int main() {
	int test_num;
	std::cin >> test_num;
 
	for (int t = 0; t < test_num; t++) {
		int branch_num;
		int base;
		int height;
		std::cin >> branch_num >> base >> height;
 
		vector<int> offsets(branch_num);
		for (int &o : offsets) { std::cin >> o; }
		std::sort(offsets.begin(), offsets.end());
 
		double total_area = 0;
		double slope = (double)base / height;
		for (int b = 0; b < branch_num; b++) {
			if (b == branch_num - 1 || offsets[b] + height <= offsets[b + 1]) {
				total_area += (double)base * height / 2;
				continue;
			}
 
			int height_diff = offsets[b + 1] - offsets[b];
			double new_base = (double)base - slope * height_diff;
			total_area += trap_area(base, new_base, height_diff);
		}
 
		cout << std::setprecision(17) << total_area << '\n';
	}
}
def trap_area(base1: float, base2: float, height: float) -> float:
	""":return: el área de un trapecio con las longitudes de base y la altura dadas"""
	return height * (base1 + base2) / 2
 
 
for _ in range(int(input())):
	branch_num, base, height = [int(i) for i in input().split()]
	offsets = sorted(int(i) for i in input().split())
	assert branch_num == len(offsets)
 
	total_area = 0
	slope = base / height
	for b in range(branch_num):
		if b == branch_num - 1 or offsets[b] + height <= offsets[b + 1]:
			total_area += base * height / 2
			continue
 
		height_diff = offsets[b + 1] - offsets[b]
		new_base = base - slope * height_diff
		total_area += trap_area(base, new_base, height_diff)
 
	print(total_area)
Fundamentos