629. Skąpiec [MISER]

Zadanie:
https://pl.spoj.com/problems/MISER

Skrócony opis problemu:

Dla danego zbioru $n$ punktów w przestrzeni 2-wymiarowej należy wyznaczyć dowolne 2 punkty, takie że okrąg utworzony na nich oraz na pierwszym punkcie z wejścia (nazwijmy go $A$) nie zawiera w sobie żadnego innego punktu (mogą jednak się znaleźć punkty na samym okręgu). Żadne 3 punkty nie są współliniowe.

Rozwiązanie naiwne:

Możemy oczywiście sprawdzić każdą parę punktów dodając do niej $A$. Dla każdej takiej trójki można sprawdzić każdy punkt czy przypadkiem nie leży w jej wnętrzu. Jeśli jakiś leży, to sprawdzamy kolejną parę.

Złożoność: $O\left(n^3\right)$, bo mamy dokładnie $\frac{(n-1)(n-2)}{2}$ par punktów jeśli pominiemy $A$, którego i tak musimy uwzględnić. A dla każdej z tych trójek musimy sprawdzić pesymistycznie każdy punkt czy nie leży on wewnątrz owego okręgu.

Rozwiązanie sprytniejsze:
Jako że interesuje nas dowolna trójka punktów spełniająca wspomniany warunek, możemy od razu wybrać punkt najbliższy $A$. Im bliżej są te 3 punkty, tym mniejsze jest koło, a więc tym większe jest prawdopodobieństwo, że nic w nim nie będzie. Czujny czytelnik zauważy, że poprzednie zdanie jest fałszywe. Możemy mieć bowiem punkty prawie współliniowe, czyli np. $A = (0, 0), B = (-50, 1), C = (50, 1)$. Powiedzmy, że $B$ i $C$ są najbliżej $A$. Jednak okrąg, który te punkty tworzą jest ogromny. Tak więc nie możemy zachłannie wybierać 2 najbliższych punktów. Po co o tym wspomniałem? Ano dlatego, że możemy jednak wykorzystać jeden najbliższy punkt i dobrać ostatni sprawdzając każdą możliwość.

Tak więc szukamy punktu leżącego najbliżej pierwszego, a następnie jak w poprzednich algorytmie, tworzymy trójkę punktów dla każdego z pozostałych $n-2$ punktów i znów liniowo sprawdzamy czy któryś z $n-3$ punktów nie leży w środku owego okręgu.

Złożoność: $O\left(n^2\right)$, gdyż na początku w $\Theta(n)$ szukamy najbliższego punktu do $A$, następnie bierzemy każdy z pozostałych $n-2$ punktów i dla każdej z takich $n-2$ trójek sprawdzamy maksymalnie $n-3$ punktów.

Rozwiązanie najsprytniejsze:
Z poprzedniego rozwiązania mamy już 2 punkty $A$ i $B$. Został nam tylko punkt $C$. Jak go znaleźć szybciej niż w $O\left(n^2\right)$? Ano możemy być zachłanni. Ale przecież napisałeś, że jak wybierzemy 2 najbliższe punkty do $A$ to nie uzyskamy najmniejszego koła! To prawda, ale możemy wziąć inne kryterium niż odległość od $A$. Co może być owym kryterium? Ano chcemy uzyskać jak najmniejsze koło, więc po prostu dla każdego punktu obliczymy promień okręgu powstałego z utworzonej trójki punktów i wybierzemy taki punkt $C$, dla którego ów promień będzie najmniejszy. Tyle. Promień ten możemy obliczyć korzystając z poniższych wzorów:
$$R = \frac{a \cdot b \cdot c}{4 \cdot P}\\ P = \sqrt{p \cdot (p-a) \cdot (p-b) \cdot (p-c)}\\ p = \frac{a+b+c}{2}$$
$R$ to właśnie promień okręgu opisanego na trójkącie, którego wierzchołkami są $A$, $B$, $C$. $a$, $b$, $c$ to długości boków tego trójkąta. $P$ to jego pole obliczone z wzoru Herona. $p$ jest natomiast połową jego obwodu.

Złożoność: $\Theta(n)$, bo na początku znajdujemy punkt najbliższy $A$ przeglądając wszystkie $n-1$ punktów, a potem znajdujemy punkt, który tworzy najmniejszy promień przeglądając $n-2$ punktów.

Algorytm:

int main()
{
        int n, i, j, k, x[10009], y[10009];
        long double a, b, c, area, p, R, min = 9e18;

        get(n, x[0], y[0]);
        for(i = 1; i < n; ++i)
        {
                get(x[i], y[i]);
                if((x[i]-x[0])*(x[i]-x[0])+(y[i]-y[0])*(y[i]-y[0]) < min)
                        min = (x[i]-x[0])*(x[i]-x[0])+(y[i]-y[0])*(y[i]-y[0]),
                        j = i;
        }
        min = 9e18;
        a = (x[0]-x[j])*(x[0]-x[j])+(y[0]-y[j])*(y[0]-y[j]);
        for(i = 1; i < n; ++i)
        {
                if(i == j)
                        continue;
                b = (x[0]-x[i])*(x[0]-x[i])+(y[0]-y[i])*(y[0]-y[i]);
                c = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
                R = b*c/(4*a*b-(a+b-c)*(a+b-c));
                if(R < min)
                        min = R,
                        k = i;
        }
        print(1, j+1, k+1);
}