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 < [email protected]> 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.
