Dany jest prostokąt o wymiarach $w \times h$, w którym zamalowano $n$ kół, $i$-te z nich o środku w punkcie $(x[i],y[i])$ i promieniu $r[i]$. Mamy $m$ zapytań; każde postaci: „Startując z wierzchołka $e$, poruszamy się wewnątrz prostokąta kołem o promieniu $R$ nie przecinając innych kół. Do których wierzchołków możemy dojść?”

Rozwiązanie dla jednego zapytania

Rozwiążemy niezależnie jedno zapytanie $e$, $R$. Zastosujemy tutaj klasyczną sztuczkę: zamiast pytać się, czy możemy przejść kołem o promieniu $R$, zwiększymy promień każdego zamalowanego koła o $R$ oraz przesuniemy każdy bok do wnętrza prostokąta o odległość $R$, a następnie będziemy pytali się, czy możemy przejść punktem (kołem o promieniu 0).

Po zwiększeniu promieni, część kół może zacząć nachodzić na inne koła i/lub boki prostokąta, tworząc większe przeszkody. Jeśli taka przeszkoda połączy dwa boki prostokąta, podzieli ten prostokąt na kawałki, między którymi nie będziemy mogli przejść. Przykładowo, połączenie przeszkodą dolnego i prawego boku spowoduje, że z dolnego-prawego wierzchołka nie będziemy mogli dojść do żadnego innego.

Możemy zatem stworzyć graf o $n+4$ wierzchołkach (po jednym dla każdego koła i boku), w którym dwa wierzchołki będą połączone krawędzią, jeśli odpowiadające im koła/boki nachodzą na siebie. Taki graf może mieć $O(n^2)$ krawędzi.

Następnie znajdujemy w grafie spójne składowe. Jeśli dwa boki są w tej samej spójnej składowej, to są one połączone przeszkodą.

Jak wyznaczyć krawędzie grafu? Jeśli mamy dwa koła $i$, $j$, to nachodzą na siebie, jeśli odległość między nimi jest mniejsza niż suma ich promieni (powiększonych o $R$), czyli $$\sqrt{ (x[i]-x[j])^2 + (y[i]-y[j])^2 } < r[i] + 2R + r[j].$$

Koło nachodzi na lewy bok, jeśli $x[i] < r[i]+2R$. Analogicznie dla pozostałych boków.

Podczas obliczeń nie trzeba używać typów zmiennoprzecinkowych, można zamiast odległości między punktami porównywać kwadraty odległości. Należy jednak uważać na możliwe przepełnienia: przykładowo suma dwóch liczb do wielkości $10^9$ mieści się w typie int, ale suma czterech liczb już nie.

Oto przykładowy kod zaliczający pierwsze podzadanie. Algorytm działa w czasie $O(mn^2)$:

const int N = 2100;
int n,m,w,h;
int x[N],y[N],r[N];
vector<int> adj[N+4];
int qe,qb,que[N+4],vis[N+4];

ull sq(int x) { return ull(x)*x; }

bool circle_circle_intersect(int i, int j, int R) {
  ull dist = sq(x[i] - x[j]) + sq(y[i] - y[j]);
  return sq(r[i] + 2*R + r[j]) > dist;
}

void add_edge(int i, int j) {
  adj[i].push_back(j);
  adj[j].push_back(i);
}

bool no_path(int i, int a, int b) {
  return vis[n + (i+a)%4] != vis[n + (i+b)%4];
}

bool can_go(int i, int j) {
  if (i == j) return true;

  if ((j+1) % 4 == i) swap(i, j);
  if ((i+1) % 4 == j) {
    return no_path(i, 0,1) && no_path(i, 0,2) && no_path(i, 0,3);
  }

  assert((i+2) % 4 == j);
  return no_path(i, 0,2) && no_path(i, 1,3)
    && no_path(i, 0,3) && no_path(i, 1,2);
}

int main() {
  scanf("%d%d%d%d",&n,&m,&w,&h);
  REP(i,n) { scanf("%d%d%d",&x[i],&y[i],&r[i]); }
  REP(q,m) {
    int R,e; scanf("%d%d",&R,&e); --e;

    REP(i,n) REP(j,i) if (circle_circle_intersect(i,j,R)) {
      add_edge(i, j);
    }
    REP(i,n) {
      int d = 2*R + r[i];
      if (x[i] < d) add_edge(i, n+3);
      if (w - x[i] < d) add_edge(i, n+1);
      if (y[i] < d) add_edge(i, n);
      if (h - y[i] < d) add_edge(i, n+2);
    }

    REP(i,n+4) vis[i] = 0;

    int C = 0;
    REP(i,n+4) if (!vis[i]) {
      qe=qb=0; que[qe++] = i;
      vis[i] = ++C;
      while (qe != qb) {
        int v = que[qb++];
        for (int u : adj[v]) if (!vis[u]) {
          que[qe++] = u;
          vis[u] = C;
        }
      }
    }
    
    REP(i,4) {
      if (can_go(e, i)) printf("%d", i+1);
    }
    printf("\n");

    REP(i,n+4) adj[i].clear();
  }
}

Rozwiązanie szybsze

Zauważmy, że jeśli możemy przejść kołem o promieniu $R$ pomiędzy pewnymi wierzchołkami, to możemy też przejść kołami o mniejszych promieniach. Możemy zatem dla każdej pary wierzchołków obliczyć wyszukiwaniem binarnym po wyniku, największy promień koła $R_{max}$, którym możemy pomiędzy nimi przejść. Takie obliczenia wstępne dla jednej pary wierzchołków będą kosztowały czas $O(n^2 \log W)$, gdzie $W$ jest ograniczeniem na wielkość współrzędnych.

Wtedy każde zapytanie będzie działało w czasie stałym (wystarczy sprawdzić, czy $R \leq R_{max}$). Złożoność algorytmu będzie zatem wynosić $O(K^2 n^2 \log W + m)$, gdzie $K=4$ jest liczbą wierzchołków i zaliczy drugie podzadanie.