On 29.10.2014 15:32, Borneq wrote:
> W dniu 2014-10-29 o 13:22, bartekltg pisze:
>> http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann
_algorithm
>>
>>
>>> Czy da się zrobić to na std::set?
>>
>> Da się.
>
> "If p is the crossing point of two segments s and t (with s below t to
> the left of the crossing), swap the positions of s and t in T"
>
> Chodzi zwłaszcza o "swap the positions", jak to się da zrobić na
> std::set jeśli jest posortowane i mamy podaną funkcję sortującą?

Bez wczytywania się dokładnie: zamień im współrzędne y.
Usuń elementy, zmodyfikuj, i wstawić je na nowo (usuwając
dosjajesz iterator, który można użyć jako hint przy wstawianiu).

Większy problem będzie z wyszukaniem miejsca na wstawienie,
bo wynik porównania powinien mieć 'kontekst' - pozycję x.
Ponieważ zmiana x w czasie algorytmu nie zmienia kolejnosci
(bo robimy to ręcznie) powinno się jakoś dać to sprytnie napisać,
ale jednak nie jest to dla mnie od razu oczywiste - jak.

Może rzeczywiście wygodniej będzie sięgnąć po boosta.

pzdr
bartekltg