PKU 2852 - Model Rocket Height

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2852

Resumo

Dadas duas retas, encontrar os pontos de ambas que minimizem a distância entre elas. Depois responder a altura (coordenada z) ponto médio entre os dois.

Solução

O enunciado desse problema é meio confuso, e acho que uma figura lá ia facilitar imensamente esse problema. Releiam e vocês verão que é isso aí que eu coloquei no resumo.

A primeira coisa que devemos fazer é colocar as coisa num sistemas de coordenadas cartesianas. Seguindo especificações do enunciado, podemos colocar o observador A no ponto $a = (0, 0, HA)$ e o observador B no ponto $b = (100, 0, HB)$.

Uma maneira de representar uma reta é através de um de seus pontos e de um vetor que indique a direção. Já temos os pontos, o vetor será calculado usando os ângulos fornecidos.

Se $\alpha$ e $\beta$ são, respectivamente, os ângulos de elevação e de azimuth, um vetor correspondente em coordenadas cartesianas é $v = \left( \cos(\alpha)\cos(\beta) , \cos(\alpha)\sin(\beta) , \sin(\alpha) \right)$. Calcule $va$ e $vb$, os ângulos das retas dos observadores A e B.

Agora fixe um ponto $x$ da reta A. O ponto da reta B que está mais próximo de $x$ será $b + <vb, x - b> vb$. Onde $<\bullet,\bullet>$ denota o produto interno usual.

Note a se percorrermos a reta A à partir de $a$ na direção de $va$, a distância de cada ponto à reta B vai diminuir, até chegar num ponto de mínimo e depois crescer. Assim podemos usar busca ternária para encontrar esse ponto de mínimo. O que encerra o problema.

Uma observação é que, se você não souber a fórmula que eu coloquei acima (ela não é muito difícil de deduzir, mas é meio chato de explicar digitando). Você pode fazer uma segunda busca ternária, para encontrar o ponto da reta B mais próximo ao ponto fixado.

Testes

Entrada

4 5.25 2.92
39.6 36.0 35.4 151.2
65.1 71.2 16.5 160.6
59.4 59.5 43.8 139.0
45.0 41.2 32.9 152.6

Saída

1: 50
2: 135
3: 119
4: 58

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License