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

@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?

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

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

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

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

@Royal_X 6241 / 2954 / 1047 Регистрация: 01.06.2021 Сообщений: 10,979
	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 3190 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,023
	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 3190 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,023
	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 3190 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,023
	13.06.2023, 21:20
	Дело не (только) в программировании, а в (потенциальном) шевелении мозгами. Есть возможность (силы, желание) "пошевелить" - шевелю, нет - пропускаю. 0

@Royal_X 6241 / 2954 / 1047 Регистрация: 01.06.2021 Сообщений: 10,979
	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 3190 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,023
	14.06.2023, 02:21
	Так как я уже ничего не понимаю (даже если до этого понимал), то оставлю просто картинку. Геометрия, брутфорс, погрешность + кадр анимации (входные данные - 6, 2, 8): 0

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