Se for como estou pensando, talvez dê para conectar cada poço à fazenda
mais próxima.
Ou melhor:
Faça todas as conexões possíveis - sim, n^2 possíveis ligações!
Some as distâncias para cada configuração, e pegue a menor delas. Esta é a
configuração pedida.
Basicamente, você verá que se dois segmentos se cruzarem, é possível
diminuir a distância entre eles.
Em 27 de abril de 2014 16:13, Rígille Scherrer Borges Menezes <
rigillesbmene...@gmail.com> escreveu:
> Gostaria de compartilhar este problema, tem uma solução bastante legal :)
> São dados 2n pontos num plano, sem três colineares. Destes pontos,
> exatamente n são fazendas F = {F1, F2, ... Fn}, os restantes são poços P =
> {P1, P2, ..., Pn}. Mostre que existe uma bijeção f : P --> F de maneira que
> nenhum segmento Pi f(Pi) cruze com outro.
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
>
--
/**************************************/
神が祝福
Torres
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
