13536. Dostawca PRK [AL_04_01]

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

Skrócony opis problemu:

Mamy $n \le 10^5$ punktów o współrzędnych z przedziału $\left<-10^9;10^9\right>$. Chcemy znaleźć sumę odległości między każdymi dwoma punktami.

Podejście naiwne:

Możemy po prostu dla zsumować wszystkie te odległości sprawdzając każdą parę punktów. Takich par jest: ${n \choose 2} = \frac{n \cdot (n-1)}{2}$.

Złożoność: $O\left(n^2\right)$.

Podejście sprytne:

Możemy zauważyć, że niektóre drogi się pokrywają. Tzn. przechodzimy przez niektóre odcinki kilka razy. Jak to zatem wykorzystać? Możemy rozpatrzeć współrzędne x i y osobno.

Weźmy zatem dowolny punkt A. Chcemy zliczyć długości wszystkich dróg poziomych (współrzędne x) prowadzących od tego punktu do pozostałych. Skoro musimy sprawdzić każdy punkt, to dla każdego z nich musimy obliczyć sumę odległości pozostałych punktów od niego szybciej niż liniowo. Możemy więc zliczyć sumę wszystkich współrzędnych x punktów.

Na powyższym rysunku suma ta wynosi $X=10$. Odległości od punktu $A$ wynoszą łącznie: 1+1+0+2+2=6. Jak je obliczyć korzystając z $X$? Otóż wszystkie drogi od punktów po prawej stronie $A$ (oznaczonych $P$) do $A$ zawierają się w drogach do osi OY ($P_i \leftrightarrow A \subset P_i \leftrightarrow OY$). Możemy zatem od każdej z dróg $P \leftrightarrow OY$ odjąć fragmenty $A \leftrightarrow OY$. Nie możemy jednak odjąć tego od $X$, gdyż $X$ zawiera oprócz punktów $P$, punkty $L$ (po lewej stronie $A$). Nawet znając moc zbioru $P$ nie bylibyśmy w stanie obliczyć jaką część $X$ one stanowią. A co gdyby nie było punktów $L$? Wtedy znalibyśmy i moc zbioru $P$, i moglibyśmy operować na $X$, gdyż wtedy $X$ składałby się z sumy współrzędnych punktów $P$ oraz współrzędnej punktu $A$. Musimy zatem operować na punktach położonych jak najbliżej osi OY, a potem je usuwać ze zbioru (żeby nie policzyć tej samej drogi 2 razy) w czasie stałym. Można to osiągnąć poprzez posortowanie punktów względem x i braniem punktu o najmniejszym x w czasie stałym, dodając odległości od niego do pozostałych punktów do ostatecznego wyniku, w czasie stałym.

Analogicznie postępowalibyśmy dla współrzędnych y.

Złożoność: $O\left(n \log n\right)$ ze względu na sortowanie.

Przykład:

(1,2), (1,5), (2,4), (3,2)

Suma wszystkich współrzędnych x: $X = 7$.

Bierzemy pierwszy punkt $A$ i dodajemy do wyniku 7-4=3. Czemu -4? Bo ustawiamy oś OY, w miejscu gdzie jest $A$, czyli o y=1. Musimy więc od każdego punktu odjąć 1, a punktów jest 4. Wywalamy punkt $A$, odejmując tym samym od $X$ wartość $x_A$, czyli 1. $X = 6$.

Bierzemy punkt $B$ i dodajemy do wyniku 6-3=3. -3, bo mamy już tylko 3 punkty, a $B$ ma taką samą współrzędną x, co $A$, więc dla każdego punktu też odejmujemy 1. Wywalamy $B$. $X = 5$.

Bierzemy $C$ i dodajemy 5-4=1. -4, bo mamy 2 punkty, ale y=2, więc 2*2=4. Wywalamy $C$. $X = 3$.

Bierzemy $D$ i dodajemy 3-3=0. Widać, że skoro mamy już 1 punkt, to nie ma żadnych dróg, jakie moglibyśmy liczyć, więc możemy pominąć w pętli ten 1 przebieg.

Tak samo dla y. Można samemu sprawdzić. Powinno wyjść dla y 11, więc łącznie 7+11=18.

Ostateczny algorytm:

int X[n], Y[n]; // zawierają współrzędne x i y punktów
int wynik = 0; // ostateczny wynik
int suma_x, suma_y; // suma współrzędnych x i y
sort(X, X+n); sort(Y, Y+n);
for(int i = 0; i < n-1; ++i) // wykonujemy n-1 razy, bo na końcu zostaje nam 1 punkt, więc i tak nie policzymy dla niego żadnej nowej drogi
{
    wynik += suma_x - (n-i)*X[i]; // dodajemy do wyniku sumę współrzędnych x, ale drogi mają kończyć się nie dla x=0, ale dla x=xA, więc odejmujemy xA tyle razy ile jest punktów; n-i, bo potem usuwamy punkt A, więc musimy zmniejszać ilość punktów
    suma_x -= X[i]; // odejmujemy xA i tym samym usuwamy punkt A
}
for(int i = 0; i < n-1; ++i)
    wynik += suma_y - (n-i)*Y[i],
    suma_y -= Y[i];
printf("%d", wynik);

Podejście sprytne nr 2:

Tak samo możemy zauważyć, że niektóre odcinki liczymy kilka razy. Tutaj również osobno rozważymy składowe pionowe odległości między punktami i poziome (współrzędne x i y).

Zajmijmy się więc odcinkami poziomymi (współrzędne x), a algorytm dla pionowych będzie taki sam. Zrzutujmy zatem wszystkie punkty na oś OX. Teraz jeszcze lepiej widać części wspólne dróg. Pozostaje zatem jedno pytanie: ile dróg przechodzi przez odcinek między kolejnymi dwoma punktami zrzutowanymi na oś OX? Załóżmy, że te 2 kolejne punkty to $x_i$ i $x_{i+1}. Odcinek$\left|x_i \ x_{i+1}\right|$przechodzi przez wszystkie drogi, których jeden koniec znajduje się przed (lub w)$x_i$a drugi za (lub w)$x_{i+1}. Dla każdej pary kolejnych odcinków wiemy, ile punktów jest do $x_i$ ($i+1$, licząc od 0) oraz od $x_{i+1}$ ($n-i-1$, licząc od 0). Tak więc każdy odcinek o końcach w $x_i$ i $x_{i+1}$ liczy się $(i+1) \cdot (n-i-1)$ razy.

Złożoność: $O\left(n \log n\right)$ ze względu na sortowanie.

Przykład:

(1,2), (1,5), (2,4), (4,2)

Kolejne współrzędne x to: 1, 1, 2, 4.

Bierzemy pierwszą parę: 1 i 1. Odcinek o długości 0, więc pomijamy.

1 i 2. Występuje: $(1+1) \cdot (4-1-1)=4$ razy. Ma długość 1, więc do wyniku dodajemy $4 \cdot 1=4$.

2 3. Występuje: $(2+1) \cdot (4-2-1)=3$ razy. Ma długość 2, więc do wyniku dodajemy $3 \cdot 2=6$.

Analogicznie postępujemy dla y. Wynik dla samych y, to: 11. Łączny wynik to $10+11=21$.

Ostateczny algorytm:

int X[n], Y[n], wynik = 0;
sort(X, X+n); sort(Y, Y+n);
for(int i = 0; i < n-1; ++i) // wykonujemy n-1 razy, bo jest n-1 odcinków, czyli par kolejnych punktów
    wynik += (X[i+1]-X[i]) * (i+1) * (n-i-1); // dodajemy do wyniku długość odcinka x_i-x_i+1 tyle razy ile występuje w drogach
for(int i = 0; i < n-1; ++i)
    wynik += (Y[i+1]-Y[i]) * (i+1) * (n-i-1);
printf("%d", wynik);