PCJ18F - Editorial

PROBLEM LINK:

Practice
Contest

Author: Prakhar Gupta
Tester: Madhav Sainanee
Editorialist: Prakhar Gupta

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Trigonometry, Basic Geometry

PROBLEM:

Given N points, find out the minimum perimeter of the rectangle with the slope of one of its sides as M such that it covers all the points.

EXPLANATION:

Since the sides of a rectangle are parallel, we can determine both the slopes as m_1 = M and m_2 = -1/M, since m_1m_2 = -1.

For every point, we find out the intercept of the line with slope m_1 passing through (x, y) on the y axis as c_i = y_i - m_1x_i.
The minimum width of the rectangle will come from the points with maximum and minimum c_i.

alt text

From the figure, c = c_{max} - c_{min} and d, the width of the rectangle, is d = c \times \cos \theta.

Since m_1 = \tan \theta, we can find \cos \theta = \frac {1} {\sqrt{1 + m_1^2}}. Therefore d = \frac{c}{\sqrt{1+m_1^2}}.

Similarly, we can find the length l from the second slope, m_2.
The perimeter is finally 2 (l + d).

There is a special case when M = 0, in which we can’t find the second slope as -1/M. In this case, the rectangle is parallel to the coordinate axes, and the perimeter is 2 (x_{max} + y_{max} - x_{min} - y_{min}).

Complexity: The time complexity is O(N) per test case.

ALTERNATE SOLUTION:

This problem can also be solved by rotating the axes by \theta = tan^{-1}(M) and following the procedure of M = 0 in the normal case, with the new coordinates of the points in the rotated axes.

You can read more about the rotation of axes here.

Complexity: The time complexity is O(N) per test case.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.
Rotation of axes solution can be found here.

2 Likes