Asked in: GOOGLE
Image of the Question
All Testcases Passed ✔
Solution
#include <iostream>
#include <vector>
using namespace std;
// ... rest of solution available after purchaseExplanation
```
To solve this problem effectively, you need to model the connectivity between circles based on whether they intersect or touch. The primary geometric insight is that two circles intersect or touch if the distance between their centers is less than or equal to the sum of their radii. In this specific problem, all circles have the same radius K, so two circles intersect or touch if the Euclidean distance between their centers is less than or equal to 2*K.
Start by visualizing each circle as a node in a graph. The goal is to connect an edge between two nodes (circles) if they intersect or touch. That means you need to compare each pair of circles and calculate the distance between their centers. If the squared distance (to avoid unnecessary square roots) between two centers is less than or equal to (2*K)^2, then an edge exists between those nodes.
Once this graph is constructed, the question becomes a connectivity problem. Given any two circles (nodes) L and R, you must determine if there exists a path between them in the graph. If a path exists, return "YES"; otherwise, return "NO". This problem can now be framed as a classic graph traversal or connected component problem.
A good way to structure the solution is to preprocess the graph and group all nodes into connected components. Two nodes belong to the same connected component if there exists a sequence of edges connecting them. You can use either a Disjoint Set Union (DSU or Union-Find) structure or Depth-First Search (DFS)/Breadth-First Search (BFS) for this purpose.
If you choose Union-Find, initialize each circle as its own set. For each pair of circles that intersect or touch, perform a union operation to merge their sets. After processing all pairs, each circle belongs to a representative set. To answer a query (L, R), simply check whether the representatives of L and R are the same. If they are, then L and R are in the same connected component, meaning Alice can travel from one to the other.
If you choose DFS/BFS, construct an adjacency list where each circle’s node lists all other nodes it connects to (i.e., those it touches or intersects with). Then, use a traversal algorithm to mark all nodes in the same connected component with a common identifier. This requires O(N + E) traversal time, where E is the number of edges (circle pairs that intersect). Once this labeling is done, queries can be answered in constant time by comparing labels of the L-th and R-th nodes.
Since the number of circles N can be large (up to a few thousand), you must consider the efficiency of your circle intersection checks. A brute force O(N^2) comparison of every pair is acceptable only for small values of N. For larger N, consider spatial partitioning techniques to reduce the number of comparisons—for example, a grid-based spatial hash or a quadtree—to quickly find potential intersecting neighbors. However, for this problem, assuming N is modest (e.g., under 2000), an O(N^2) approach is likely sufficient.
Key computational steps are:
1. Precompute the squared distances between each pair of circles.
2. For each pair, check if their squared distance is ≤ (2*K)^2.
3. If so, mark them as connected.
4. Use Union-Find or DFS/BFS to group connected circles.
5. For each query (L, R), check whether L and R belong to the same group.
Finally, convert the result of each query into a "YES" or "NO" string based on connectivity and return the answers.
This approach transforms a geometry problem into a graph problem by leveraging the idea of spatial intersection to form graph edges and then uses classic connected component detection to efficiently answer multiple reachability queries.
```