## PROBLEM LINKS

## DIFFICULTY

CAKEWALK

## PREREQUISITES

Simple math, Triangle inequality

## PROBLEM

We have two markets S and T. We want to build two restaurants. The markets and restaurants can be considered as points in 2D Cartesian plane. Arrange markets and the restaurants in such a way that:

- The distance between S and T is D.
- The distance between S and one of the restaurants is D
_{S}. - The distance between T and the other restaurant is D
_{T}. - The distance between the two restaurants is minimized.

Determine the minimum distance between the two restaurants.

## QUICK EXPLANATION

To solve this kind of problem, it is best to try sketching many placements of the objects, and try spotting some easy patterns that lead to the best result. The answer to this problem is very short: max(0, D - D_{S} - D_{T}, D_{S} - D_{T} - D, D_{T} - D_{S} - D).

## EXPLANATION

We can divide the input into 4 cases:

**Case 1**. D ≥ D_{S} + D_{T}

The optimal placement of the objects is in a straight line as follows.

+----------D----------+ / \ S R R T \ / \ / +-D_{S}-+ +-D_{T}-+

Here, the markets are represented by S and T while restaurants are represented by R’s. The minimum distance between the points is D - D_{S} - D_{T}.

**Case 2**. (D_{S} + D_{T} > D) and (D + D_{S} > D_{T}) and (D + D_{T} > D_{S})

The lengths are said to satisfy the triangle inequality. In this case, we can always form a triangle as follows.

+----------D----------+ / \ S T \ / \ / D_{S}D_{T}\ / \ / \ / R

Here, the two restaurants are located in the exact same position and thus represented by a single R. The distance is of course 0.

**Case 3**. Triangle inequality does not hold and D_{S} ≥ D + D_{T}

The optimal placement is as follows.

+----------D_{S}---------+ / \ S T R R \ / \ / +-D--+ +-D_{T}-+

The distance between the restaurants is D_{S} - D - D_{T}.

**Case 4**. Triangle inequality does not hold and D_{T} ≥ D + D_{S}

The optimal placement is as follows.

+----------D_{T}---------+ / \ R R S T \ /\ / +-D_{S}-+ +-D--+

The distance between the restaurants is D_{T} - D - D_{S}.

So, the code for this solution is very simple, just considering all four cases and printing the appropriate value. However, one can actually unite the four cases in one single expression: max(0, D - D_{S} - D_{T}, D_{S} - D_{T} - D, D_{T} - D_{S} - D). Try to prove it yourselves!

## SETTER’S SOLUTION

Can be found here.

## TESTER’S SOLUTION

Can be found here.