On Sunday, May 15, 2016 at 8:33:24 AM UTC+2, Wojciech Muła wrote:
> On Sunday, May 15, 2016 at 8:03:02 AM UTC+2, slawek wrote:
> > Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> > najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej);
>
> To raczej nie zadziała, jak myślisz.
>
> w.

Propozycja Sławka mnie się skojarzyła z problemem stabilnych małżeństw.
Problem 'sparowania po najmniejszej odległości' wydaje się nawet
łatwiejszy, bo jeśli facet y najbardziej preferuję kobietę x, to także
kobieta x najbardziej preferuje faceta y. Jednak w tym wątku chodzi o
najmniejszą sumę, a nie o stabilność par - stabilność chyba nie
gwarantuje najmniejszej sumy?


Pozdrawiam