## Editorial for DMOPC '21 Contest 9 P3 - Terrible Trains

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

For each query, create 2-D points and 2-D points , where is the shortest distance from to . Then, we need to find two points and , one from each set, so that and . For each point in the first set, the set of valid points in the second set forms a rectangular shape in the 2-D plane. Thus, this problem is equivalent to checking whether there is any intersection between a set of points and rectangles, which can be done with line sweep.

**Time Complexity:**

#### Subtask 2

Firstly, if or , then it is automatically possible — simply add the new edge between the two stations that are not yet close enough (if they exist). Otherwise, the key observation is that it is always optimal for the endpoints of the additional edge to lie on the shortest path from to and the shortest path from to , possibly with and swapped. After all, if the endpoints do not lie on these shortest paths, they can always be pulled towards them without increasing any of the relevant distances. Secondly, given this fact, note that it is necessary for . It turns out that this is also sufficient: the endpoints can be walked along the shortest paths towards the pair of stations that is too far, keeping the left side of the inequality constant while decreasing the distance between the further pair. Since this decrease occurs smoothly and continuously, the closer pair will not suddenly become too far. Thus, each query can be answered in time.

**Time Complexity:**

## Comments