# BOI 2016 Park solution
What makes this problem difficult is that moving a circle around is very continuous, and thus difficult to deal with. The key idea to discretize it is as follows: suppose we are at the top-left corner. The only way we cannot reach the bottom-left corner is if there is a sequence of circles from the left to right wall, where for every pair of adjacent circles, we cannot squeeze between them.


We cannot squeeze between two circles iff the distance between them is smaller than our diameter.

This statement is not entirely true; it might also be the case that we are blocked by a sequence going from the left wall to the top wall or bottom wall.

## Subtask 1
Suppose our diameter is $d$. To solve the problem, we can create a graph where every wall and circle is a node. There is an edge between two nodes if the distance between them is less than $d$. We have enough time to check for edges between all $O(N^2)$ pairs of circles. To check if we can go from the top-left corner to the bottom-left one, we check if any of the following is true:
- The left wall's node is in the same connected component as the top wall
- Left wall is in same connected component as right wall
- Left wall is in same connected component as bottom wall

Note that it's not a problem if an edge goes through another circle, so we do not need to check for this. You might need to use an epsilon when checking whether two circles intersect.

For other corners, similar logic applies.

The challenge now is to avoid an excessive amount of code. If done naively, there are 12 cases (same corner to same corner is trivial), in which you have to do 3 checks for each. Instead, for each query I always compute all reachable corners. I start out assuming that I can reach all corners. Then, I iterate over all ${4 \choose 2}=6$ possible wall connections, and for each one check how it affects reachability. My code is as follows:

int bottomwall = n;
int leftwall = n + 1;
int topwall = n + 2;
int rightwall = n + 3;

int bottomleft = 1;
int topleft = 8;
int topright = 4;
int bottomright = 2;
...

int c = corner[current_query];
c = 1 << c;

int qans = 1|2|4|8;
if (uf.find(leftwall)==uf.find(topwall)) {
    if (c==topleft) qans = topleft;
    else qans &= ~topleft;
}

if (uf.find(topwall)==uf.find(rightwall)) {
    if (c==topright) qans = topright;
    else qans &= ~topright;
}

if (uf.find(rightwall)==uf.find(bottomwall)) {
    if (c==bottomright) qans = bottomright;
    else qans &= ~bottomright;
}

if (uf.find(bottomwall)==uf.find(leftwall)) {
    if (c==bottomleft) qans = bottomleft;
    else qans &= ~bottomleft;
}

if (uf.find(leftwall)==uf.find(rightwall)) {
    if (c == bottomleft || c == bottomright) qans &= ~(topleft | topright);
    else qans &= ~(bottomleft | bottomright);
}

if (uf.find(topwall)==uf.find(bottomwall)) {
    if (c == bottomleft || c == topleft) qans &= ~(topright | bottomright);
    else qans &= ~(bottomleft | topleft);
}
// qans is now a bitmask of all reachable corners

There are hopefully cleaner ways to do this, but anything more than this would probably be very painful.

Because we build the graph for every query, we get $O(MN^2)$, enough for subtask 1.

## Full solution
To optimize the previous solution to get full points, we can realize that what we are basically doing is the following: we build a graph with the distance between every pair of circles/wall, with weight equal to the distance. To answer every query, we need to answer "is there a path from $a$ to $b$ using only edges with weight $< d$"?

There are many solutions to this problem, with the simplest one probably being to first sort all queries by $d$. Then, we maintain a union-find, which starts empty. When we need to answer queries for a particular $d$, we add all edges with weight $< d$. When we process the next one, we can keep the edges already in the union-find. Now we only need to add some new edges. In total, every edge is added exactly once.

In total, we get $O(Q\log(Q)+N^2\log(N^2))$ due to sorting.

The solution to subtask 2 is most likely to build a maximum spanning tree of all edges, since we might as well only use those. In a sense, they are the "earlist edges that connect new components". We can now answer every query in $O(N)$ by doing a DFS on the tree. It's a strange subtask, however, since we can easily get away with only doing a DFS from each wall in $O(4N)$ time, which then solves the entire problem in $O(N^2\log(N^2)+Q)$.

## Even faster
Using the idea of building an MST, we can reduce the complexity to $O(N^2\log(N^2)+Q)$ and answer queries online. To go even further, the MST can be built in $O(N\log(N))$ time using either a sweep or constructing a voronoi diagram. In IOI-style contests, voronoi diagrams are highly unlikely to show up, but it might be good practice to implement the sweep; sweeps are very common in both computational geometry and other query-like problems. This gives $O(N\log(N)+Q)$ and is likely optimal.