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] + 2 R + r [j] .$

Koło nachodzi na lewy bok, jeśli $x [i] < r [i] + 2 R$ . 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 (m n^{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_{m a x}$ , 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_{m a x}$ ). 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.