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).


Był bardzo podobny, słabszy*) problem:
Też dwa zbiory A,B punktów na płaszczyźnie,
chcemy je sparować tak, aby linie łączące je nie przecinały się.

Kołacze mi się po głowie, że rozwiązaniem było znajdowanie
przecięcia i likwidowaniem go, poprzez zamianę sparowania.

Nie pamiętam jednak szczegółowy, a jest tam taki problem,
więc nie potrafię odtworzyć złożoności.
Problem w tym, że relaksacja może spowodować zwiększenie się
liczby przecięć (to nie przeszkadza w poprawności, rozwiązanie znajdzie**).


*) sparowanie o minimalnej sumie długości nie ma przecięć,
ale rozwiązanie bez przecięć nie musi być minimalne:
A B
| |
| |
| |
| |
B A

**) Zbiór możliwych wartości sumy jest skończony,
każda operacja prostowania kolizji zmniejsza tę odległość.
Jeśli nie mamy rozwiąznia=> jest kolizja=> mozemy poprawić.
Ale nie zrobimy więcej niż ileśtam kroków.

pzdr
bartekltg