Problema de Outubro de 2004: Sunny Mountains

O primeiro problema que proponho é um que apareceu na MIUP 2004 e que achei o mais fácil. É o problema A, "Sunny Mountains".

During their honeymoon, Mrs and Mr Smith went to the Himalayas. How they were surprised when they observed that, during the sunset, all the snow touched by the sunbeams turned red.

Such a magnificent landscape leaves everyone plenty of emotion, but Mr Smith's number obsession overcame all this. He rapidly began evaluating distances, which made Mrs Smith quite upset.

Problem

For the sake of simplicity, consider that, during the sunset, the sunbeams are horizontal and assume that the landscape is described by the set of coordinates of the mountain peaks and cols. This can be depicted by the following figure. A landscape, in this context, is then a sequence of peaks and cols (i.e., only a col follows a peak and conversely).

Note that, in this picture, the sunny mountainsides are emphasized by bold lines and the coordinates of the landscape are emphasized by bold points.

Thus, the goal of this problem is to calculate the total length in meters of the bold lines.

For this task consider that: (1) for all coordinates (x, y), 0 <= x <= 30000 and 0 <= y <= 8848; (2) the unit is the meter; (3) all the X-coordinates are pair-wise distinct; (4) the leftmost point has 0 as X-coordinate and the rightmost point has 0 as Y-coordinate; (5) The total number of coordinates given is n <= 100.

Input

Output

Sample Input

11

1100 1200

0 500

1400 100

600 600

2800 0

400 1100

1700 600

1500 800

2100 300

1800 700

2400 500

Sample Output

1446.34

É mais fácil olhar primeiro para esta imagem:

O que o programa faz é:
- lê os pontos do input e guarda-os no mapa scape
- percorre os pontos de trás para a frente
- mantém uma variável miny que corresponde à altura mínima de um pico para que tenha uma área que não esteja sombreada
- para cada ponto nessas condições, soma a linha que apanha sol ao total

O que queremos somar cada vez que encontramos um pico nas condições referidas é a linha a vermelho. Sabemos as coordenadas dos pontos marcados a preto (as do mais alto estão no iter e as do mais baixo, que lhe fica à direita, estão no iter2). Com estas coordenadas podemos achar as medidas dos lados do triângulo verde; vamos chamar à altura a e à largura b. À altura do triângulo laranja (que é o que interessa) vamos chamar dy e à largura dx. A recta vermelha saca-se com o teorema de Pitágoras: h = sqrt(dx^2 + dy^2). O dy é a altura do ponto mais alto menos a altura mínima (miny). O dx é b menos b2, onde b2 é a largura de outro triângulo com os mesmos ângulos internos que o triângulo verde. Para esse triângulo, a altura a2 é igual a miny menos a altura do ponto mais baixo (é a parte da altura do triângulo verde que não tem o laranja por cima). Usando a relação a/b = a2/b2, sacamos b2 com b2 = (a2*b)/a. Com isto já temos o dx e o dy e é só somar ao total, e actualizar o miny para a altura do ponto mais alto. Ao início, miny é 0.

Código em C++:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

map<int, int> scape;

int main()
{
	double total;
	int xtotal;
	int i, x, y;
	double dx, dy;
	map<int, int>reverse_iterator iter, iter2;
	double miny;
	double b2, a, b, a2;

	cin >> xtotal;

	for (i = 0; i < xtotal; i++) {
		cin >> x >> y;
		scape[x] = y;
	}

	miny = 0;
	total = 0;
	for (iter = scape.rbegin(); iter != scape.rend(); iter++) {
		if (iter->second <= miny) {
			continue;
		}

		iter2 = iter;
		iter2--;
		dy = iter->second - miny;
		a = iter->second - iter2->second;
		b = iter2->first - iter->first;
		a2 = miny - iter2->second;
		b2 = (a2 * b) / a;
		dx = b - b2;
		total += sqrt((dx * dx + dy * dy));

		miny = iter->second;
	}

	printf("%0.2lf\n", total);

	return 0;
}

Alguns comentários: podíamos usar o triângulo laranja e sacar directamente o dx, mas não me ocorreu :) seria exactamente a mesma coisa, não afectava a performance do algoritmo. Uma coisa que já podia melhorar a performance é o scape, que usei um mapa de int para int mas podia bem ser uma lista, que faz mais sentido. Com o mapa, a iteração de trás para a frente é tão eficaz como na lista, mas a ler os pontos já não é, porque inserir à frente ou a trás de uma lista requer tempo constante, enquanto que num mapa requer O(log n), onde n é o número de elementos no mapa. Ou seja, para inputs com muitos pontos podia notar-se um impacto, mas como o número de pontos é <= 100 neste problema, isto não faz diferença nenhuma.

Uma "inconsistência" que fiz foi usar o cin para ler e o printf para escrever. Não é boa prática misturar o stdio com o iostream, mas o cin é muito mais versátil e simples de usar para ler e o printf para escrever. O problema é que não domino bem os iomanips de C++ :) e não sabia bem como definir a precisão para 2 casas decimais, e para não perder tempo usei o printf. Não custava nada usar o cout, mas o que se pede neste caso não é código bonito, é código que funcione e é entregá-lo o mais rápido possível!