Как найти максимальную площадь прямоугольника

Given a rectangle of dimensions L and W. The task is to find the maximum area of a rectangle that can be circumscribed about a given rectangle with dimensions L and W.
 

Examples:

Input: L = 10, W = 10
Output: 200

Input: L = 18, W = 12
Output: 450

Approach: Let below is the given rectangle EFGH of dimensions L and W. We have to find the area of rectangle ABCD which is circumscribing rectangle EFGH. 
 

In the above figure: 
If then as GCF is right angled triangle. 
Therefore, 

=> 
=> 
Similarly, 

Now, The area of rectangle ABCD is given by: 
 

Area = AB * AD 
Area = (AE + EB)*(AH + HD) …..(1) 
 

According to the projection rule: 
AE = L*sin(X) 
EB = W*cos(X) 
AH = L*cos(X) 
HD = W*sin(X) 
 

Substituting the value of the above projections in equation (1) we have: 
 

Now to maximize the area, the value of sin(2X) must be maximum i.e., 1. 
Therefore after substituting sin(2X) as 1 we have, 

 

Below is the implementation of the above approach: 
 

Time Complexity: O(1) 
Auxiliary Space: O(1)
 

1. шаг — записываем формулу площади (объема) (S=a*b).
2. шаг — выражаем одну сторону фигуры через другую. Например в задаче «Проволока длинной 76 см согнута в прямоугольник , найдите длину сторон, при которых площадь прямоугольника наибольшая» была указана связь между сторонами прямоугольника — известный периметр, что позволило выразить одну сторону через другую и периметр (b  = frac{P}{2}-a)), аналогично и в задаче Периметр основания прямоугольного параллелепипеда  .
3. шаг — подставляем подученную формулу в формулу порщади (объема)(например для прямоугольника (S=a*b = a*(frac{P}{2}-a) = a*frac{P}{2}-a^2).
4. шаг — находим первую производную и приравниваем ее к нулю (S’= (a*frac{P}{2}-a^2)` = frac{P}{2}-2*a = 0)
5. шаг — решаем полученное уравнение и находим корни уравнения (т.е. значения неизвестного при котором значение функции (производной) равно 0). Это и будет ответ, т.е. длина стороны при которой площадь будет наибольшей (аналогично и с объемом) (frac{P}{2}-2*a = 0 => a = frac{P}{4}).
6. шаг — желательно проверить истинность полученного решения — подставить найденное значение в функцию (площади или объема) и рассчитать ее, а для сравнения взять соседнее значение стороны (больше или меньше) и так же подставить. Если площадь получится меньше, значит задача решена верно, если нет, то нужно искать ошибку.

P.S. вопросы и пожелания пишите в личку.

Некоторые заметки слишком большие, чтобы поместить их в комментарий (хотя это не предполагает очевидного алгоритма):

Суть (РЕДАКТИРОВАНО): Как минимум две вершины прямоугольника максимальной площади должны лежать на границе многоугольника (т.е. вдоль ребра или в вершине). А если прямоугольник максимальной площади не является квадратом, то по крайней мере три вершины должны лежать на границе многоугольника.

Я доказал это для себя в четыре шага:

Примечание №1: Хотя бы одна вершина прямоугольника максимальной площади всегда будет лежать на границе многоугольника. Это довольно очевидно, но доказательство может выглядеть следующим образом (путем противоречия): Предположим, у вас есть «максимальный» прямоугольник, ни одна вершина которого не лежит на границе многоугольника. Это означает, что вокруг каждой из его вершин есть хотя бы немного места. Поэтому вы можете немного расширить прямоугольник, что противоречит его максимальности.

Примечание #2: По крайней мере две вершины прямоугольника максимальной площади всегда будут лежать на границе многоугольника. Доказательство можно провести следующим образом (опять же через противоречие): Предположим, у вас есть «максимальный» прямоугольник с одной вершиной на границе (что гарантируется примечанием №1). Рассмотрим два ребра, не смежных с этой вершиной. Поскольку их конечные точки не лежат на границе, вокруг каждой из них есть немного места. Поэтому любое из этих ребер может быть «выдавлено» немного, увеличивая площадь многоугольника и противореча его максимальности.

Примечание №3: Существуют две диагонально противоположные вершины прямоугольника максимальной площади, которые лежат на границе многоугольника. (Из замечания #2 мы знаем, что их как минимум две, но не обязательно, что они лежат напротив друг друга). Но, опять же по противоречию, если бы только две граничные вершины были смежными, то противоположное ребро (ни одна из вершин которого не лежит на границе) можно было бы немного выдавить, увеличив площадь прямоугольника и опровергнув его максимальность.

Примечание #4: (РЕДАКТИРОВАНО) Если прямоугольник максимальной площади не является квадратом, то три его вершины будут лежать на границе многоугольника.

Для доказательства предположим, что это не так, т.е. прямоугольник максимальной площади не является квадратом, но только две его вершины лежат на границе многоугольника. Я покажу, как построить прямоугольник большей площади, противоречащий максимуму.

Назовем вершины прямоугольника A, B, C и D. Без потери общности предположим, что B и D — это две вершины, которые находятся на границе многоугольника. Поскольку A и C находятся на внутренней стороне многоугольника, вокруг них есть свободное пространство (на рисунке ниже оно представлено кружками вокруг A и C). Теперь нарисуйте окружность вокруг прямоугольника и сдвиньте точки A и C немного по окружности на ту же величину (чтобы получились A' и C', изображенные ниже) так, чтобы новый прямоугольник A'BC'D был более квадратным, чем исходный прямоугольник. Этот процесс создает новый прямоугольник, который также находится внутри исходного многоугольника и имеет большую площадь. Это противоречие, поэтому доказательство завершено.

Чтобы поверить в это доказательство, нужно убедить себя, что площадь прямоугольника, вписанного в круг, увеличивается по мере того, как он становится «более квадратным» (то есть разница между длинами ребер становится меньше). Также нужно, чтобы многоугольник был выпуклым, чтобы все новые линии находились внутри него. Возможно, есть и другие мелкие детали, о которых забыли, но я уверен, что все они работают.

Если честно, я не нашел конкретного теста, на котором программа падает, но хочу кое-что отметить.

В первую очередь при решении олимпиадной задачи по информатике надо внимательно посмотреть на ограничения, после чего решить задачу максимально просто и быстро. В данном случае N <= 105, поэтому линейный алгоритм тут абсолютно ни к чему. Так что вам не стоило использовать очереди минимумов, причем так, что в худшем случае вы создадите массив на 3*10^7 элементов, который никак не обработается за тайм лимит на питоне. Лучше напишите самый очевидный и простой кубический алгоритм:

n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
ans = a[0][0] * a[0][1]
for left in range(n):
    for right in range(left, n):
        min_h = a[left][1]
        sum_w = 0
        for i in range(left, right + 1):
            min_h = min(min_h, a[i][1])
            sum_w += a[i][0]
        area = min_h * sum_w
        ans = max(ans, area)
print(ans)

Если вдруг он не пройдет по времени и религия не позволяет вам писать на C++, то sum_w можно считать префиксными суммами, и это ускорит программу почти в два раза. Если вдруг даже так она упадет с TLE, то только тогда извращайтесь с очередями минимумов на сжатых координатах или пишите дерево отрезков минимумов на питоне (пожалуйста, не надо).

И желаю вам больше не выкладывать код и задачи с отборочных соревнований, пока они не закончатся (если они еще не закончились), потому что это запрещено правилами и является очень неспортивным поведением.

Upd: Как заметил комментатор ниже, вы скорее всего некорректно вставили условие (и скорее всего не прочитаете даже этот ответ), так что мое решение является неверным. Однако ваше собственное решение точно также не укладывается в стандартную секунду, так как при максимальном тесте вы не успеете создать массив на 3*10^7 элементов на питоне.

Решение для ограничений N <= 10^5, Wi <= 3*10^4 — это ваше решение с очередями минимумов, но со сжатием координат.