[Algorytmy] Skrajne elementy zbioru

xredom · Post autor: **xredom** » 3 sie 2015, o 08:58

Witam jak mogę znaleźć skrajny element zbioru opartego na układzie współrzędnych. Wiedząc że średnia wszystkich elementów \(\displaystyle{ [x,y]}\) tego zbioru jest środkiem do wyznaczenia okręgu o promieniu równym długości odcinka między środkiem a najbardziej skrajnym elementem tego zbioru.

Post autor: **Afish** » 3 sie 2015, o 09:28

Policz średnią a następnie znajdź najbardziej oddalony punkt.

xredom · Post autor: **xredom** » 3 sie 2015, o 10:20

Afish pisze:Policz średnią a następnie znajdź najbardziej oddalony punkt.

Ok czyli nie ma jakiegoś szybszego rozwiązania ? Bo dysponując tablicą setek tysięcy elementów to trochę zajmie miejsca w pamięci.

Post autor: **Afish** » 3 sie 2015, o 10:31

O ile dobrze rozumiem problem, to nie ma. Skoro każdy punkt jest kandydatem na bycie skrajnym, to nie da się go pominąć bez dodatkowej informacji (typu uporządkowanie kolekcji), więc musimy sprawdzić każdy.

flashion · Post autor: **flashion** » 4 sie 2015, o 22:15

xredom pisze:
Afish pisze:Policz średnią a następnie znajdź najbardziej oddalony punkt.
Ok czyli nie ma jakiegoś szybszego rozwiązania ? Bo dysponując tablicą setek tysięcy elementów to trochę zajmie miejsca w pamięci.

Co zajmie miejsca w pamięci? Trzymasz jedynie najlepsze dotychczasowe rozwiązanie.
Żeby trochę przyspieszyć, licz tylko kwadraty odległości.