On Saturday, February 13, 2016 at 12:04:32 AM UTC+1, bartekltg wrote:
> On 12.02.2016 21:03, M.M. wrote:
> > On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
> >> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> >> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> >>> To szukasz algorytmu, czy heurystyki?
> >>
> >> Jak zwał tak zwał.
> >
> > Apropo heurystyk. Co by bylo, gdyby N razy wyrzucić M losowo wybranych
> > punktów i odpalić dokładny algorytm po każdym wyrzuceniu? Algorytm
> > dla 50 punktów zadziała bardzo szybko. Ostatecznie można wyrzucić K
> > punktów które najrzadziej były w rozwiązaniu i znowu odpalić algorytm
> > dokładny.
>
> Dla 50 (czy 2000) punktów podany ścisły algorytm O(n^3 +)
> jest całkowicie wysatrczający.
> Pytanie, co zrobić jak jest ich 500 000 albo 10^9;-)
>
> pzdr
> bartekltg

Inny pomysł.

Szukamy min i max dla points[i].x i points[i].y .

Mamy prostokąt (min.x,min.y) (max.x,max.y). Wewnątrz prostokąta
robimy siatkę MxM prostokątów. Każdy prostokąt traktujemy jako
punkt, tyle że ważony, jego waga jest równa ilości punktów wewnątrz, a
środek to średnia arytmetyczna punktów (zawartych w nim, rzecz jasna).

Gdy M damy 30, to mamy tylko 900 punktów. Liczymy algorytmem dokładnym.
Potem na wszystkich punktach szorujemy okręgiem w okolicach pierwszego
rozwiązania.

Ciekawe jakby to działało w praktyce na różnych danych.

Pozdrawiam