PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
simple
PREREQUISITES:
none
PROBLEM:
There are three squares, each with side length a placed on the x-axis. The coordinates of centers of these squares are (x1, a/2), (x2, a/2) and (x3, a/2) respectively. All of them are placed with one of their sides resting on the x-axis.
You are allowed to move the centers of each of these squares along the x-axis (either to the left or to the right) by a distance of at most K. Find the maximum possible area of intersections of all these three squares that you can achieve.
SOLUTION
First of all, let us change the problem from finding integersections of squares to that of lines. So, we treat each square of length a as a line segment of length a. We find the maximum length of the intersection of the three lines segments and multiply it by a to find the area of the square.
Suppose we sort the squares with respect to their center coordinates. You can observe that the middle line segment doesn’t matter. If the first and third line segment can intersect by some length, then second segment can always be moved in order to obtain same length intersection.
Now, you have to find the length of the intersection of the first and the third line segment if each is allowed to move by a length of K. The idea is to move the first segment to right and the third to left.
For that, we first check whether they can fully intersect. Otherwise, we move the first segment to the right by a distance of K and the third segment to the left by a distance of K and find their intersection length.
Here is one possible Java Implementation of the approach
int[] x = new int[3];
for (int i = 0; i < 3; ++i) {
x[i] = in.nextInt();
}
Arrays.sort(x);
int d = Math.max(0, x[2] - x[0] - k * 2);
double area = Math.max(0, (a - d)) * (double) a;
out.println(area);