# Baltic OI 16 Park

Author: Michael Cao

## TL;DR

Draw lines between circles and to borders, and use DSU to answer queries offline.

## Intuition

In this problem, we're given a park with circles of differing radii and asked whether some circle can move from a corner of the park to another corner. Upon first glance, this task seems quite challenging and probably involves some not-so-fun geometry. However, the final solution turns out to be quite nice, and not too hard to implement either.

Let's call the circle you are moving around between exits $x$. We claim that $x$ can move between two circles $a$ and $b$ as long as $dist(a,b)−a_{r}−b_{r}≤x_{r}$, where $x_{r}$ denotes the radius of $x$, $a_{r}$ and $b_{r}$ denote the radius of $a$ and $b$ and $dist(a,b)$ denotes the distance between the centers of $a$ and $b$. Also, let's add horizontal and vertical line segments from each border of the park to each circle with the distance between them as well.

Finally, observe that you can go from exit $e_{1}$ to exit $e_{2}$ as long as there isn't some chain of line segments with weight $≤x_{r}$ that completely blocks off the path between exits. For example, you can go from the top-right exit to the bottom-left exit as long as there isn't a chain of line segments from the top border to the bottom, top to right, bottom to left, or left to right.

## Creating a Graph

Now, you have some circles with weights between each other. Let's transform each of the line segments we defined before into an edge, and each circle and border into a node, creating $n_{2}+4n$ edges overall and $n+4$ nodes.

The problem of checking whether we can go between two exits now becomes checking, for some $r$, whether edges with weight $≤r$ connect certain borders (this involves some casework).

## Offline Queries and DSU

To efficently answer queries of whether two borders are connected, let's process them in order of increasing $x_{r}$ and store a DSU. Now, we can add edges one by one as long as their weight $≤x_{r}$, and then check connectivity between the border nodes.

### Warning!

## Code

1#include <bits/stdc++.h>2using namespace std;34using ll = long long;56using vi = vector<int>;7#define pb push_back8#define rsz resize9#define all(x) begin(x), end(x)10#define sz(x) (int)(x).size()

## Give Us Feedback on Baltic OI 16 Park!

### Join the Discussion!

Feel free to voice your thoughts in the comments section.