https://pl.spoj.com/problems/PTWPZ096
Skrócony opis problemu:
Mamy listę $n$ kolorów modelu RGB, czyli w postaci trójki liczb z przedziału $\left<0; 255\right>$. Mamy następnie $m$ zapytań będących również pojedynczymi kolorami RGB. Dla każdego koloru z zapytania należy znaleźć najbliższy mu kolor z listy, którą dostaliśmy na początku. Odległość jest w metryce euklidesowej (czyli $odl(col1, col2) = \sqrt{\left(col1.r-col2.r\right)^2 + \left(col1.g-col2.g\right)^2 +\left(col1.b-col2.b\right)^2}$). Jeśli 2 punkty będą w tej samej odległości, to należy wybrać ten z większą składową czerwoną. Jeśli i one będą równe - z większą składową zieloną i ew. z większą składową niebieską. Kolory rozłożone są równomiernie na obszarze, który zajmują (a nie np. tylko na zewnętrznych ścianach lub prawie tylko w centrum).
Rozwiązanie nr 1:
Na początku warto skupić się na ostatnim zdaniu skróconej treści. Kolory rozłożone są równomiernie. W każdym zadaniu takie zdanie coś nam od razu sugeruje. Mianowicie, struktury (oraz algorytmy) z pesymistyczną złożonością liniową będą działały w czasie logarytmicznym. Np. weźmy sobie niezrównoważone drzewo binarne. Jeśli dodamy do niego elementy: $1, 2, 3, \ldots, x$ to każda operacja będzie miała złożoność liniową, bo będziemy musieli przejść wszystkie wierzchołki, jako że podane liczby są posortowane. Tak więc to drzewo byłoby po prostu taką ścieżką. Jeśli jednak wiedzielibyśmy, że liczby zostaną podane "równomiernie", czyli losowo (nie po kolei), to dodawanie do drzewa zajmie nam logarytmiczną ilość operacji. I tak jest tutaj.
A zatem, jaka struktura ma pesymistyczny czas dodawania liniowy, a średni czas logarytmiczny, jeśli mówimy o trójkach liczb? Ano jest to octree, czyli drzewo ósemkowe, którego działania nie będę tutaj opisywał. Jeśli ktoś ma problem z wyobrażeniem sobie jak będzie wyglądało dodawanie kolejnych punktów, to polecam zrobić to zadanie jakbyśmy mieli pary liczb, a nie trójki, czyli wykorzystać quadtree (drzewo czwórkowe). Zamiana na koniec programu z quadtree na octree to 5-10 minut, a mniej czasu będzie trzeba poświęcić na myślenie i debuggowanie.
Trochę szczegółów implementacyjnych. Na początku musimy dodać wszystkie $n$ kolorów z listy do drzewa. Możemy robić to pojedynczo, ale wydaje mi się, że bardziej optymalnie jest dodać wszystkie naraz (tak jakby). A zatem mamy sobie listę $n$ punktów i wywołujemy funkcję $build$ podając ją i jej rozmiar jako parametry. Jeśli rozmiar wynosi 1 (został nam 1 punkt) to w danym węźle drzewa umieszczamy ów kolor. W przeciwnym wypadku będziemy musieli podzielić ten węzeł na 8 części. Tworzymy sobie więc tablicę 8 list. Każda z nich będzie zawierała punkty które będą szły do jednej z 8 części (czyli jednego z 8 potomków węzła). Następnie, dla każdego z dziecka sprawdzamy czy lista punktów, które powinny się w nim znaleźć jest niezerowa. Jeśli jest, to tworzymy to dziecko i wywołujemy rekurencyjnie $build$ dla nowej listy wierzchołków. To tak w skrócie. Nie będę opisywał krok po kroku algorytmu, a jedynie ideę.
Następnie, dla każdego zapytania musimy znaleźć najbliższy mu kolor. Tutaj też można by posłużyć się rekurencją, ale postanowiłem wykorzystać stos i iterację. Na początku wrzucamy na stos roota, czyli węzeł odpowiadający całej przestrzeni $\left<0; 255\right>^3$. Dalej będę w pętli zdejmował ze stosu węzły aż stos będzie pusty. Dla każdego węzła będziemy sprawdzali czy jego odległość od koloru z zapytania jest mniejsza niż dotychczasowego najlepszego koloru. Jeśli tak, to oczywiście aktualizujemy najlepszy kolor. Na koniec, jeśli węzeł nie jest liściem, każde jego niepuste dziecko będziemy dodawali na stos.
Można wyczuć, że jest to póki co zbyt wolny algorytm, bo sprawdzimy praktycznie wszystkie kolory. Trzeba pomijać węzły (czyli sześciany), które są odpowiednio daleko od koloru z zapytania. No i jest na to prosty sposób. Mamy sobie kolor z zapytania (czyli punkt z 3 współrzędnymi) i mamy jakąś najlepszą dotychczasową odległość. A więc jeśli jakiś punkt ma być lepszy, to musi być wewnątrz lub na sferze, której środkiem jest kolor z zapytania, a promieniem najlepsza odległość. Wystarczy więc w czasie stałym sprawdzić czy nasz węzeł (sześcian) ma jakiś punkt wspólny z ową sferą. Jeśli tak - dodajemy go na stos, jeśli nie - nie ma po co.
Złożoność: $O(m \cdot n)$, bo dla każdego zapytania pesymistycznie przejdziemy około $n$ kolorów. Jednak dzięki równomiernemu rozłożeniu kolorów w przestrzeni, średni czas jest rzędu $m \cdot \log n$ operacji i wystarcza to do zaliczenia zadania.
Algorytm:
struct color
{
int r, g, b;
color() : r(-1), g(-1), b(-1) { }
color(int red, int green, int blue)
{
r = red;
g = green;
b = blue;
}
color& operator = (const color &c)
{
r = c.r;
g = c.g;
b = c.b;
return *this;
}
};
bool doesCubeIntersectSphere(color C1, color C2, color S, int R)
{
int dist_squared = R;
if (S.r < C1.r) dist_squared -= (S.r-C1.r)*(S.r-C1.r);
else if (S.r > C2.r) dist_squared -= (S.r-C2.r)*(S.r-C2.r);
if (S.g < C1.g) dist_squared -= (S.g-C1.g)*(S.g-C1.g);
else if (S.g > C2.g) dist_squared -= (S.g-C2.g)*(S.g-C2.g);
if (S.b < C1.b) dist_squared -= (S.b-C1.b)*(S.b-C1.b);
else if (S.b > C2.b) dist_squared -= (S.b-C2.b)*(S.b-C2.b);
return dist_squared >= 0;
}
struct octree
{
octree *children[10];
color col, smallest, biggest;
octree() : children()
{
col = color(-1, -1, -1);
smallest = color(0, 0, 0);
biggest = color(255, 255, 255);
}
void build(color *palette, int size)
{
if(size == 1 || (smallest.r == biggest.r && smallest.g == biggest.g && smallest.b == biggest.b))
{
col = palette[0];
return;
}
color *child_palette[8];
for(int i = 0; i < 8; ++i)
child_palette[i] = new color[size];
int child_sizes[8] = {0, 0, 0, 0, 0, 0, 0, 0};
for(int i = 0; i < size; ++i)
{
int code = 0;
if(palette[i].r > biggest.r+smallest.r>>1)
code |= 1;
if(palette[i].g > biggest.g+smallest.g>>1)
code |= 2;
if(palette[i].b > biggest.b+smallest.b>>1)
code |= 4;
child_palette[code][child_sizes[code]++] = palette[i];
}
for(int i = 0; i < 8; ++i)
if(child_sizes[i])
{
children[i] = new octree();
children[i]->smallest = color(smallest.r+(i%2)*((biggest.r+smallest.r>>1)+1-smallest.r), smallest.g+((i>>1)%2)*((biggest.g+smallest.g>>1)+1-smallest.g), smallest.b+(i>3)*((biggest.b+smallest.b>>1)+1-smallest.b));
children[i]->biggest = color((biggest.r+smallest.r>>1)+(i%2)*((biggest.r+smallest.r>>1)+1-smallest.r), (biggest.g+smallest.g>>1)+((i>>1)%2)*((biggest.g+smallest.g>>1)+1-smallest.g), (biggest.b+smallest.b>>1)+(i>3)*((biggest.b+smallest.b>>1)+1-smallest.b));
children[i]->build(child_palette[i], child_sizes[i]);
}
}
color nearest_neighbour(int red, int green, int blue, color best, int smallestDist)
{
octree *node;
int sum;
stack<octree*> stos;
stos.push(this);
while(!stos.empty())
{
node = stos.top(); stos.pop();
sum = (red-node->col.r)*(red-node->col.r)+(green-node->col.g)*(green-node->col.g)+(blue-node->col.b)*(blue-node->col.b);
if(node->col.r != -1 && (sum < smallestDist || (sum == smallestDist && node->col.r > best.r) || (sum == smallestDist && node->col.r == best.r && node->col.g > best.g) || (sum == smallestDist && node->col.r == best.r && node->col.g == best.g && node->col.b > best.b)))
best = node->col,
smallestDist = sum;
else if(node->col.r == -1)
{
for(int i = 0; i < 8; ++i)
if(node->children[i] != NULL && doesCubeIntersectSphere(node->children[i]->smallest, node->children[i]->biggest, color(red, green, blue), smallestDist))
stos.push(node->children[i]);
}
}
return best;
}
};
int main()
{
int n, a, b, c, mapa[17000000];
octree *root = new octree();
color palette[n];
get(n);
for(int i = 0, j = 0; i < n; ++i)
{
get(a, b, c);
if(!mapa[(a<<16)+(b<<8)+c])
{
mapa[(a<<16)+(b<<8)+c] = 1;
palette[j].r = a; palette[j].g = b; palette[j].b = c;
++j;
}
}
root->build(palette, n);
get(n);
while(n--)
get(a, b, c),
print(root->nearest_neighbour(a, b, c, palette[0], (a-palette[0].r)*(a-palette[0].r)+(b-palette[0].g)*(b-palette[0].g)+(c-palette[0].b)*(c-palette[0].b)));
}
Rozwiązanie nr 2:
Kolejnym, bardzo podobnym rozwiązaniem, jest wykorzystanie kd-drzewa. Złożoność pesymistyczna również liniowa. W implementacji trochę trudniejsze. Nie będę opisywał tego rozwiązania - wspominam tylko, że jest możliwość.
Rozwiązanie nr 3:
Najlepszym rozwiązaniem jest zastosowanie diagramu Woronoja. Diagram ów można zbudować za pomocą algorytmu Fortuny, wykorzystującego technikę geometryczną jaką jest zamiatanie. Po zbudowaniu owego diagramu na każde zapytanie otrzymamy odpowiedź w pesymistycznym czasie $O(\log n)$.
Brak komentarzy:
Prześlij komentarz