Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.53/40: Рейтинг темы: голосов - 40, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 10.07.2020
Сообщений: 11

Найти площадь максимального прямоугольника, который можно вырезать из фигуры

10.07.2020, 14:33. Показов 8781. Ответов 23

Студворк — интернет-сервис помощи студентам
Прямоугольники
Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0,0), вправо на оси OX вплотную друг за другом. Требуется найти M — площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N (1≤N≤105). Далее идут N строк. В каждой строке содержатся два числа: ширина и высота i-го прямоугольника (1<wi≤3⋅104, 0≤hi≤3⋅104).

Формат выходных данных

Выведите искомое число M.
3
4 3
2 1
2 5 12

3
4 3
2 1
3 5 15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stack>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int* a = new int[n];
 
    stack <int> stack;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
    
        if (!stack.empty() && stack.top() < a*b)
        {
            stack.pop();
        }
        
        stack.push(a * b);
    }
    cout << stack.top();
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.07.2020, 14:33
Ответы с готовыми решениями:

Найдите площадь наибольшего квадрата, который можно вырезать из оставшейся фигуры
Из всех углов квадрата со стороной 5 вырезали по квадратику со стороной 1. Найдите площадь наибольшего квадрата, который можно вырезать из...

Найти минимальную площадь прямоугольника, в который можно поместить все заданные прямоугольники
В двумерном пространстве заданы n прямоугольников с вершинами в целочисленных координатах и сторонами параллельными осям координат. Найти...

Определить максимальную площадь прямоугольника, который можно вписать в данную гистограмму
Вам дается массив целых неотрицательных чисел -- количество и высота столбцов гистограммы. Вам необходимо определить максимальную площадь...

23
0 / 0 / 0
Регистрация: 10.07.2020
Сообщений: 11
12.07.2020, 12:53  [ТС]
Студворк — интернет-сервис помощи студентам
К сожалению, программа не всегда работает корректно:

3
4 3
2 1
3 5

Выдает: 17
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
12.07.2020, 13:27
мой косяк, исправил
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(t_rect_iter i = rects.begin(); i!=rects.end(); i++)
    {
        Mtmp = i->S;
        for (t_rect_iter j = i+1 ; j!=rects.end(); j++)
        {
 
            if (j->height < i->height)
            break;
            Mtmp = Mtmp + j->S;
        }
 
        if (Mtmp>M)
            M=Mtmp;
    }
0
 Аватар для zayats80888
6354 / 3525 / 1428
Регистрация: 07.02.2019
Сообщений: 9,008
12.07.2020, 13:30
Цитата Сообщение от dmitrii2000 Посмотреть сообщение
Пишет неверный формат вывода
Если ты про мой вариант, то попробуй заменить все double на unsigned long long
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
12.07.2020, 13:34
щас дотестирую, сорри
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
12.07.2020, 13:34

Найти площадь прямоугольника, который принадлежит обеим осям координат
Подскажите алгоритм! Есть два прямоугольника в декартовой системе исчисления. Их стороны параллельны осям координат. Как найти площадь...

Сколько из прямоугольника можно вырезать квадратов
Работа ведется на языке Си в среде Visual Studio 2013 Дан прямоугольник со сторонами a,b. Сколько из такого прямоугольника можно...

Найти стороны прямоугольника наибольшей площади, который можно вписать в эллипс (x^(2)/25)+(y^(2)/9)=1
Найти стороны прямоугольника наибольшей площади, который можно вписать в эллипс (x^(2)/25)+(y^(2)/9)=1 Заранее спасибо.

Круг какой площади можно вырезать из полученного прямоугольника?
Из круга радиусом R вырезан прямоугольник, большая сторона которого равна А. Круг какой площади можно вырезать из полученного...

Сколько квадратов со стороной 30 можно вырезать из данного прямоугольника?
дан прямоугольник размером 647х170. Сколько квадратов со стороной 30 можно вырезать из него?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
24
Ответ Создать тему
Новые блоги и статьи
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно. • На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru