On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <b...@g...com> wrote:
>> więc być mozę da się prościej. Na szybko nie widzę.
>
> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej); usuń
> parę. Powtarzaj aż do skutku. Rób to kolejno od najbliższej pary.
> Odległości par możesz obliczyć i posortować, a potem usuwać już
> nieobecne. Całość celuje w O(N log N).

Kontrprzykład:

A1 <-2m-> B1 <-1m-> A2 <-2m-> B2

Optymalne rozwiązanie wiąże A1-B1 B2-A2 na kwotę 4m.

Rozwianie zachłanne daje A1-B2 B1-A2 na kwotę 6m.

pzdr
bartekltg