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 . We claim that can move between two circles and as long as , where denotes the radius of , and denote the radius of and and denotes the distance between the centers of and . 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 to exit as long as there isn't some chain of line segments with weight 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 edges overall and nodes.

The problem of checking whether we can go between two exits now becomes checking, for some , whether edges with weight 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 and store a DSU. Now, we can add edges one by one as long as their weight , and then check connectivity between the border nodes.

Warning!

When computing distance between two circles, make sure to subtract the radius of both. We want the distance between the borders, not the centers.

Code

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5
6using vi = vector<int>;
7#define pb push_back
8#define rsz resize
9#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.