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

@Ocefsa · Регистрация: 18.12.2022

Студворк — интернет-сервис помощи студентам

Добрый день, смысл задачи такой: есть квадратный стол, есть прямоугольная скатерть, которая не может покрыть весь стол. Нам нужно найти максимальную площадь покрытия. У квадрата и прямоугольника одинаковый центр. Более того, наибольшая длина скатерти меньше диагонали квадрата. На вход подаются сторона квадрата и стороны прямоугольника. Я не рассматриваю случай, когда скатерть помещается внутри стола. Я так понимаю, что прямоугольник нужно крутить, и где-то от 0 до 45 градусов. Но у меня нет идеи как это осуществить. Есть ограничения по времени и памяти: 1с и 256мб.

@Royal_X · 13.06.2023, 15:19

Ocefsa, столько памяти хватит даже, чтобы запустить GTA SA.

@KSergey9 · 13.06.2023, 15:28

Сообщение от Ocefsa

Но у меня нет идеи как это осуществить.

1) Вывести формулу площади фигуры при пересечении прямоугольника и квадрата в зависимости от угла поворота
2) Найти её экстремумы; экстремумы функции всегда располагаются там, где производная функции равна 0; производная функция там явно вычислится без сложностей аналитически.

@Ocefsa · 13.06.2023, 16:06 **[ТС]**

KSergey9, Не очень поняла, как вывести эту формулу

@gunslinger · 13.06.2023, 16:09

Насколько я понимаю (верно?), максимальная площадь "покрытия" получается при повороте на 45⁰.
По крайней мере по следующему рисунку такие выводы напрашиваются.

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

Объяснение:
У большего прямоугольника (который расположен под углом в 45⁰) площадь вне квадрата равна 4, у меньшего она тоже = 4.
Если меньший прямоугольник повернуть на 45⁰, его внешняя площадь уменьшится (точное значение нужно считать).
А если повернуть больший прямоугольник на 45⁰, его внешняя площадь увеличится (тут считать проще, она станет равна примерно 4,68629).

Если это так, то остальное дело техники.

@Ocefsa · 13.06.2023, 16:18 **[ТС]**

gunslinger, боюсь, вы взяли для примера большую сторону прямоугольника равную диагонали квадрата, такой случай не совсем то, что я хотела бы выяснить, я бы хотела знать, что делать, еслм сторона строго меньше. Я пробовала взять просто площадь, когда он на 45 градусах, но ответ был неправильным.

Добавлено через 1 минуту
gunslinger, допустим, сторона квадрата была 6, 2 и 8 были бы стороны прямоугольника

@KSergey9 · 13.06.2023, 16:24

Нарисовать картинку на бумажке: квадрат, на нём повернутый на угол альфа прямоугольник.
А дальше курс геометрии средней школы: разбить фигуру пересечения на прямоугольнички и треугольнички и найти площади каждой такой фигурки. Потом площади сложить.

Добавлено через 5 минут
э, не, надо не площать фигуры пересечения напрямую искать.
Видно, что за пределы квадрата от прямоугольника торчат треугольники, 4 шт, по 2 одинаковых
Проще найти площади этих треугольников - их всего 4 (и только 2 из них разных), после чего от общей площади прямоугольника отнять площади этих торчащих треугольников.
Так проще будет формулу получить. (не забыть учесть, что при некоторых размерах и углах поворота торчать и и вовсе только 2 треугольника будут)

@gunslinger · 13.06.2023, 16:30

Ocefsa, я в курсе, что бОльшая сторона прямоугольника должна быть меньше диагонали квадрата.
Рисунок лишь в качестве примера привел (на нем было проще и легче принцип показать).
И что значит "взять просто площадь"? Нужно из площади прямоугольника (она при повороте не меняется) вычесть площади 4-х треугольников (которые вне квадрата). Либо найти площадь одного треугольника и умножить на 4.

Добавлено через 1 минуту
Это если мое предположение про 45⁰ верно.

@Ocefsa · 13.06.2023, 16:38 **[ТС]**

gunslinger, извините, неправильно выразилась, я имела в виду, что считала площадь, когда прямоугольник под углом в 45 градусов, я пробовала вычитать треугольники, а также делить фигуру покрытия, ответ был одинаковым в обоих случаях, но неправильным

@gunslinger · 13.06.2023, 17:21

Пока сделал такой набросок для нуля градусов и с учетом всех (вроде как?) частных случаев:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double OuterSquareOfRectArea (double SquareSide, double RectSide1, double RectSide2)
{
  double MaxRectSide = (RectSide1 > RectSide2) ? RectSide1 : RectSide2;
  double MinRectSide = (RectSide1 < RectSide2) ? RectSide1 : RectSide2;
 
  // если наибольшая сторона прямоугольника не больше стороны квадрата
  if (MaxRectSide <= SquareSide)
    return RectSide1 * RectSide2;  // весь прямоугольник внутри квадрата
 
  // если наименьшая сторона прямоугольника не меньше стороны квадрата
  if (MinRectSide >= SquareSide)
    return SquareSide * SquareSide;  // весь квадрат внутри прямоугольника
 
  // если наибольшая сторона прямоугольника не меньше диагонали квадрата
  if (MaxRectSide >= sqrt(2) * SquareSide)
    return -1;  // возвращаем -1
 
  // угол поворота прямоугольника = 0 градусов
  return SquareSide * MinRectSide;
}

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

@TheCalligrapher · 13.06.2023, 18:21

Сообщение от Ocefsa

Но у меня нет идеи как это осуществить.

Это задача по геометрии, а не по программированию. Сначала ее нужно решить, а потому уже написать элементарную программу. Если решения нет, то и о программе речи быть не может.

@KSergey9 · 13.06.2023, 19:16

gunslinger , вы с каком классе учитесь?

@gunslinger · 13.06.2023, 20:40

KSergey9, если бы в школе учились всю жизнь, то должен был перейти в 37-ой класс в этом году.
А если серьезно, то потому и смутно теорию помню, так как было это давно.

В итоге вот что получилось:

Варианты 1 и 2a отбрасываем (почему - очевидно же или нет?). Я проверял вариант 3 (поворот на 45⁰) и вариант без поворота.
По идее нужно еще проверить (для чистоты эксперимента) вариант 2b, но что-то лень, не хватает мозгов, вариант не внушает доверия (нужное подчеркнуть).

Итоговый код (возможно, перемудрил, спорить не буду):

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
double InnerSquareOfRectArea (double SquareSide, double RectSide1, double RectSide2)
{
  double MaxRectSide = (RectSide1 > RectSide2) ? RectSide1 : RectSide2;
  double MinRectSide = (RectSide1 < RectSide2) ? RectSide1 : RectSide2;
  double RectDiag = hypot(MaxRectSide, MinRectSide), SquareDiag = hypot(SquareSide, SquareSide);
 
  // если наибольшая сторона прямоугольника не больше стороны квадрата
  if (MaxRectSide <= SquareSide)
    return RectSide1 * RectSide2;  // весь прямоугольник внутри квадрата
 
  // если наименьшая сторона прямоугольника не меньше стороны квадрата
  if (MinRectSide >= SquareSide)
    return SquareSide * SquareSide;  // весь квадрат внутри прямоугольника
 
  // если наибольшая сторона прямоугольника не меньше диагонали квадрата
  if (MaxRectSide >= SquareDiag)
    return -1;  // возвращаем -1
 
  // находим высоту "выпирающего" (за границы квадрата) треугольника (ВТ)
  // при повороте прямоугольника на 45 градусов
  double height = cos(atan2(-MinRectSide, MaxRectSide) + atan(1)) * RectDiag / 2 - SquareSide / 2;
 
  // если height <= 0, то прямоугольник целиком помещается в квадрат
  if (height <= 0)
    return RectSide1 * RectSide2;
 
  // сторона ВТ (он равнобедренный)
  double side = height / sin(atan(1));
 
  // тогда считаем площадь ВТ (он прямоугольный)
  double TriangleSquare = side * side / 2;
 
  // площадь прямогольника (ПП) внутри квадрата = ПП - 4 площади ВТ
  double InnerRectSquare = RectSide1 * RectSide2 - 4 * TriangleSquare;
 
  // площадь прямоугольника при угле поворота = 0 градусов
  double RectSquare = SquareSide * MinRectSide;
 
  // выводим максимальное из InnerRectSquare и RectSquare значение
  return (InnerRectSquare > RectSquare) ? InnerRectSquare : RectSquare;
}

Для данных 6, 2, 8 (из поста №6) ответ 14,8528137423857 (такое значение получаем при повороте прямоугольника на 45⁰).

@KSergey9 · 13.06.2023, 21:12

Сообщение от gunslinger

А если серьезно, то потому и смутно теорию помню, так как было это давно.

Тогда, на мой взгляд, такие задачи есть смысл по возможности пропускать. Они к программированию не имеют отношения, программирование в них элементарное, суть в нахождении формул через знание геометрии.

@gunslinger · 13.06.2023, 21:20

Дело не (только) в программировании, а в (потенциальном) шевелении мозгами.
Есть возможность (силы, желание) "пошевелить" - шевелю, нет - пропускаю.

@Royal_X · 13.06.2023, 23:53

Либо я не понимаю условие задачи, либо вы тут создали проблему на пустом месте. Задача - детский сад.
Пусть на вход подаются сторона квадрата a и сторона прямоугольника b, которая не превышает a * sqrt(2). По условию, сторона прямоугольника меньше диагонали квадрата, но я буду рассматривать "меньше равно", т.к. вариант "меньше" является глупостью для чисел с плавающей запятой.
Независимо от введенных значений, вторая сторона прямоугольника будет равна a * sqrt(2). Кстати, стороны прямоугольника могут быть равны, ибо квадрат это частный случай прямоугольника.
Т.е. скатерть это прямоугольник с размерами b × a * sqrt(2), расположенная под углом 45 градусов. В случае, когда пользователь ввел b = a * sqrt(2), получаем прямоугольник a * sqrt(2) × a * sqrt(2), который полностью покрывает квадрат.
Найти площадь покрытой части не составляет труда. От площади квадрата отнимаем площади двух равных треугольников.

@gunslinger · 14.06.2023, 02:21

Так как я уже ничего не понимаю (даже если до этого понимал), то оставлю просто картинку.
Геометрия, брутфорс, погрешность + кадр анимации (входные данные - 6, 2, 8):

@TheCalligrapher · 14.06.2023, 03:54

Сообщение от Royal_X

Независимо от введенных значений, вторая сторона прямоугольника будет равна a * sqrt(2).
...
Т.е. скатерть это прямоугольник с размерами b × a * sqrt(2),

С чего бы это вдруг? Согласно условию, обе стороны скатерти вводятся извне.

Сообщение от Royal_X

Т.е. скатерть это прямоугольник с размерами b × a * sqrt(2), расположенная под углом 45 градусов.

Почему именно 45?

@Royal_X · 14.06.2023, 07:54

TheCalligrapher, да, был невнимателен. Почему-то прочёл, мол вводится только одна сторона прямоугольника.

Добавлено через 11 минут
TheCalligrapher, прямоугольник нужно разместить диагонально, поэтому и угол 45° + 90° × n. Только так получим максимальную площадь покрытия.

@Royal_X · 14.06.2023, 09:36

TheCalligrapher, был невнимателен. Почему-то прочёл, мол вводится только одна сторона прямоугольника.

Сообщение от TheCalligrapher

Почему именно 45?

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Ocefsa 0 / 0 / 0 Регистрация: 18.12.2022 Сообщений: 4

	На квадратном столе разместить прямоугольную скатерть с максимальной площадью 13.06.2023, 14:59. Показов 1962. Ответов 44 Метки квадрат, планиметрия, площадь, прямоугольник (Все метки) Добрый день, смысл задачи такой: есть квадратный стол, есть прямоугольная скатерть, которая не может покрыть весь стол. Нам нужно найти максимальную площадь покрытия. У квадрата и прямоугольника одинаковый центр. Более того, наибольшая длина скатерти меньше диагонали квадрата. На вход подаются сторона квадрата и стороны прямоугольника. Я не рассматриваю случай, когда скатерть помещается внутри стола. Я так понимаю, что прямоугольник нужно крутить, и где-то от 0 до 45 градусов. Но у меня нет идеи как это осуществить. Есть ограничения по времени и памяти: 1с и 256мб. 0

@Royal_X 6118 / 2813 / 1038 Регистрация: 01.06.2021 Сообщений: 10,252
	13.06.2023, 15:19
	Ocefsa, столько памяти хватит даже, чтобы запустить GTA SA. 0

@Ocefsa 0 / 0 / 0 Регистрация: 18.12.2022 Сообщений: 4
	13.06.2023, 16:06 [ТС]
	KSergey9, Не очень поняла, как вывести эту формулу 0

@gunslinger place status here 3185 / 2219 / 640 Регистрация: 20.07.2013 Сообщений: 5,999
	13.06.2023, 16:09
	Насколько я понимаю (верно?), максимальная площадь "покрытия" получается при повороте на 45⁰. По крайней мере по следующему рисунку такие выводы напрашиваются. Объяснение: У большего прямоугольника (который расположен под углом в 45⁰) площадь вне квадрата равна 4, у меньшего она тоже = 4. Если меньший прямоугольник повернуть на 45⁰, его внешняя площадь уменьшится (точное значение нужно считать). А если повернуть больший прямоугольник на 45⁰, его внешняя площадь увеличится (тут считать проще, она станет равна примерно 4,68629). Если это так, то остальное дело техники. 0

@Ocefsa 0 / 0 / 0 Регистрация: 18.12.2022 Сообщений: 4
	13.06.2023, 16:18 [ТС]
	gunslinger, боюсь, вы взяли для примера большую сторону прямоугольника равную диагонали квадрата, такой случай не совсем то, что я хотела бы выяснить, я бы хотела знать, что делать, еслм сторона строго меньше. Я пробовала взять просто площадь, когда он на 45 градусах, но ответ был неправильным. Добавлено через 1 минуту gunslinger, допустим, сторона квадрата была 6, 2 и 8 были бы стороны прямоугольника 0

@KSergey9 631 / 526 / 104 Регистрация: 05.08.2022 Сообщений: 2,810
	13.06.2023, 16:24
	Нарисовать картинку на бумажке: квадрат, на нём повернутый на угол альфа прямоугольник. А дальше курс геометрии средней школы: разбить фигуру пересечения на прямоугольнички и треугольнички и найти площади каждой такой фигурки. Потом площади сложить. Добавлено через 5 минут э, не, надо не площать фигуры пересечения напрямую искать. Видно, что за пределы квадрата от прямоугольника торчат треугольники, 4 шт, по 2 одинаковых Проще найти площади этих треугольников - их всего 4 (и только 2 из них разных), после чего от общей площади прямоугольника отнять площади этих торчащих треугольников. Так проще будет формулу получить. (не забыть учесть, что при некоторых размерах и углах поворота торчать и и вовсе только 2 треугольника будут) 1

@gunslinger place status here 3185 / 2219 / 640 Регистрация: 20.07.2013 Сообщений: 5,999
	13.06.2023, 16:30
	Ocefsa, я в курсе, что бОльшая сторона прямоугольника должна быть меньше диагонали квадрата. Рисунок лишь в качестве примера привел (на нем было проще и легче принцип показать). И что значит "взять просто площадь"? Нужно из площади прямоугольника (она при повороте не меняется) вычесть площади 4-х треугольников (которые вне квадрата). Либо найти площадь одного треугольника и умножить на 4. Добавлено через 1 минуту Это если мое предположение про 45⁰ верно. 0

@Ocefsa 0 / 0 / 0 Регистрация: 18.12.2022 Сообщений: 4
	13.06.2023, 16:38 [ТС]
	gunslinger, извините, неправильно выразилась, я имела в виду, что считала площадь, когда прямоугольник под углом в 45 градусов, я пробовала вычитать треугольники, а также делить фигуру покрытия, ответ был одинаковым в обоих случаях, но неправильным 0

@KSergey9 631 / 526 / 104 Регистрация: 05.08.2022 Сообщений: 2,810
	13.06.2023, 19:16
	gunslinger , вы с каком классе учитесь? 0

@gunslinger place status here 3185 / 2219 / 640 Регистрация: 20.07.2013 Сообщений: 5,999
	13.06.2023, 21:20
	Дело не (только) в программировании, а в (потенциальном) шевелении мозгами. Есть возможность (силы, желание) "пошевелить" - шевелю, нет - пропускаю. 0

@Royal_X 6118 / 2813 / 1038 Регистрация: 01.06.2021 Сообщений: 10,252
	13.06.2023, 23:53
	Либо я не понимаю условие задачи, либо вы тут создали проблему на пустом месте. Задача - детский сад. Пусть на вход подаются сторона квадрата a и сторона прямоугольника b, которая не превышает *a sqrt(2). По условию, сторона прямоугольника меньше диагонали квадрата, но я буду рассматривать "меньше равно", т.к. вариант "меньше" является глупостью для чисел с плавающей запятой. Независимо от введенных значений, вторая сторона прямоугольника будет равна a * sqrt(2). Кстати, стороны прямоугольника могут быть равны, ибо квадрат это частный случай прямоугольника. Т.е. скатерть это прямоугольник с размерами b × a * sqrt(2), расположенная под углом 45 градусов. В случае, когда пользователь ввел b = a * sqrt(2), получаем прямоугольник a * sqrt(2) × a * sqrt(2)**, который полностью покрывает квадрат. Найти площадь покрытой части не составляет труда. От площади квадрата отнимаем площади двух равных треугольников. 1

@gunslinger place status here 3185 / 2219 / 640 Регистрация: 20.07.2013 Сообщений: 5,999
	14.06.2023, 02:21
	Так как я уже ничего не понимаю (даже если до этого понимал), то оставлю просто картинку. Геометрия, брутфорс, погрешность + кадр анимации (входные данные - 6, 2, 8): 0

@Royal_X 6118 / 2813 / 1038 Регистрация: 01.06.2021 Сообщений: 10,252
	14.06.2023, 07:54
	TheCalligrapher, да, был невнимателен. Почему-то прочёл, мол вводится только одна сторона прямоугольника. Добавлено через 11 минут TheCalligrapher, прямоугольник нужно разместить диагонально, поэтому и угол 45° + 90° × n. Только так получим максимальную площадь покрытия. 0