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

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

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

@KSergey9 · 14.06.2023, 13:34

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

Геометрия, брутфорс, погрешность + кадр анимации

Формулу вывести (площади перекрытия от угла) лично не сумел. Пичаль.

Тупой бротфорс показал такие же результаты: макс. площадь при 45. Надо же... интуитивно не совсем это очевидно.

Кликните здесь для просмотра всего текста

Небольшое пояснение:
а) кручу квадрат, не прямоугольник
б) поточечно считаю площадь только в половине координатной сетки

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
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cmath>
 
// A - сторона квадрата
// B, C - размеры прямоугольника
int calcS(int A, int B, int C, double alfa)
{
    alfa = alfa / 90 * M_PI / 2;  // на входе угол в градусах, для удобства
    A /=  2;
    B /=  2;
 
    int S = 0;
    
    const int range = std::max(std::max(B, C) * 1.0, sqrt(2.) * A) + 1;
    
    for (int x = -range; x <= range; x++)
        for (int y = 0; y <= range; y++)
        {
            if (abs(x) < C && abs(y) < B)   // если попадаем в прямоугольник
            {
                if (abs(x * cos(alfa) + y * sin(alfa)) < A)
                    if (abs(-x * sin(alfa) + y * cos(alfa)) < A)     // если попадаем в квадрат
                        S++;
            }
        }
 
    return S * 2;
}
 
 
int main()
{
    int A = 350;
    int B = 80;
    int C = 400;
    
    int maxS = 0;
    double maxAlfa = -1;
    for (double alfa = 0; alfa < 90; alfa += 0.2)
    {
        std::cout<<"Calc alfa=" << alfa << " ...\n";
        int S = calcS(A, B, C, alfa);
        if (S > maxS)
        {
            maxS = S;
            maxAlfa = alfa;
        }
        std::cout<<" ... S=" << S << " maxS=" << maxS << " maxAlfa" << maxAlfa << '\n';
    }
 
    return 0;
}

@gunslinger · 14.06.2023, 13:58

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

Формулу вывести (площади перекрытия от угла) лично не сумел. Пичаль.

Я и не хотел (или да, не смог). Больше интересовало доказательство того, почему и при каком угле площадь максимальна (для исходных условий задачи). Но до этого я не дошел. Хотя и не особо оно мне, в принципе, нужно.
Насчет 45⁰ я высказывал предположения. Потом решил "перебором" проверить, чтобы убедиться.

И касаемо формул - код к той картинке из поста №17 не выложил, исправляюсь.

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
42
43
44
45
46
47
48
  int SquareSide = 6, RectSide1 = 2, RectSide2 = 8;
  int shift = 150, mult = 50;
  Canvas->Rectangle(shift - 1, shift - 1, shift + mult * SquareSide + 1, shift + mult * SquareSide + 1);
 
  double angle = atan2(RectSide1, RectSide2);
  double angle_minus = angle - atan(1) / 45 * Tag, angle_plus = angle + atan(1) / 45 * Tag;
  double cos_minus = cos(angle_minus), cos_plus = cos(angle_plus);
  double sin_minus = sin(angle_minus), sin_plus = sin(angle_plus);
 
  int center_x = shift + SquareSide * mult / 2, center_y = center_x;
 
  double MaxRectSide = (RectSide1 > RectSide2) ? RectSide1 : RectSide2;
  double MinRectSide = (RectSide1 < RectSide2) ? RectSide1 : RectSide2;
  double RectDiag = hypot(MaxRectSide, MinRectSide) * mult / 2;
 
  Canvas->MoveTo(center_x - RectDiag * cos_minus - 1, center_y - RectDiag * sin_minus - 1);
  Canvas->LineTo(center_x - RectDiag * cos_plus - 1, center_y + RectDiag * sin_plus + 1);
  Canvas->LineTo(center_x + RectDiag * cos_minus + 1, center_y + RectDiag * sin_minus + 1);
  Canvas->LineTo(center_x + RectDiag * cos_plus + 1, center_y - RectDiag * sin_plus - 1);
  Canvas->LineTo(center_x - RectDiag * cos_minus - 1, center_y - RectDiag * sin_minus - 1);
 
  Canvas->Brush->Color = clGreen;
  int x = shift + mult * SquareSide / 2, y = x;
  Canvas->FloodFill(x, y, Canvas->Pixels[x][y], fsSurface);
 
  double count = 0;
  for (int i = shift - 1; i <= shift + mult * SquareSide + 1; i++)
    for (int j = shift - 1; j <= shift + mult * SquareSide + 1; j++)
      if (Canvas->Pixels[i][j] == clGreen)
        count++;
 
  Canvas->Brush->Color = Color;
 
  double area = count / mult / mult;
  static double max_area = 0, tmp_angle = 0;
 
  if (Tag == 50)
    Tag = 0;
  Tag++;
 
  if (area > max_area)
  {
    max_area = area;
    tmp_angle = Tag;
  }
 
  Label->Caption = "Area = " + String(area) + ", angle = " + String(Tag);
  Label2->Caption = "MaxArea = " + String(max_area) + " (angle = " + String(tmp_angle) + ")";

@KSergey9 · 14.06.2023, 14:04

Не по теме:

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

код к той картинке из поста №17

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

@Royal_X · 14.06.2023, 14:29

gunslinger, но ведь не всегда угол 45 градусов дает макс площадь. Например, если стороны прямоугольника равны стороне квадрата, то лучше не поворачивать:

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

@gunslinger · 14.06.2023, 14:37

KSergey9, предвзятое отношение я вижу. Зачем рисовать в консоли, если есть более удобные средства?
И "чат жпт" в билдер не встроен (плюс в России жпт заблочен, да мне он вряд ли нужен в любом случае). Код приходится (хотя никто не заставляет) самому писать.

Насчет формул - в посте №13 я вывел формулу для 45⁰. Так как на 99% уверен, что это ответ к задаче (не забывая, что иногда поворот не нужен, это я тоже учел), зачем нужна общая формула, зависящая от угла? Ну и доказательство условия(-ий) максимума площади - это по идее в другой раздел форума.

Плюс из серии "критикуешь - предлагай". Где общие формулы (площади от угла) без "ручного" подсчета пикселей для любых допустимых условиями входных данных? Где доказательство, что площадь максимальна при 45⁰ (или 0⁰)? Либо я слепой, либо просьба ткнуть носом.
Благодарю за внимание (старался быть сдержанным, в интернете мне это не сложно, есть время думать, когда пишешь).

Добавлено через 1 минуту
Royal_X, я тут уточнил, что, скорей всего, макс. площадь при 45⁰ или 0⁰.

Добавлено через 2 минуты
В посте №13 использовал это в коде. Но "открыто" об этом почему-то не говорил (наверно, думал, что это очевидно, или вообще не думал).
Если не 0⁰, то 45⁰.

Добавлено через 2 минуты

C++
33
34
35
36
37
38
39
40
  // площадь прямогольника (ПП) внутри квадрата = ПП - 4 площади ВТ
  double InnerRectSquare = RectSide1 * RectSide2 - 4 * TriangleSquare;
 
  // площадь прямоугольника при угле поворота = 0 градусов
  double RectSquare = SquareSide * MinRectSide;
 
  // выводим максимальное из InnerRectSquare и RectSquare значение
  return (InnerRectSquare > RectSquare) ? InnerRectSquare : RectSquare;

Там же старался учесть "особые" случаи (тот же пост №13 или ранее №10).

@Royal_X · 14.06.2023, 14:39

gunslinger, т.е. ты считаешь и при 0° и при 45°, но выводишь ту площадь, что больше?

@KSergey9 · 14.06.2023, 14:42

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

но ведь не всегда угол 45 градусов дает макс площадь. Например, если стороны прямоугольника равны стороне квадрата, то лучше не поворачивать:

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

Поэтому обсуждаем лишь менее очевидный случай частичного перекрытия.

@gunslinger · 14.06.2023, 14:47

Royal_X, получается так. Это я в тот момент не был достаточно уверен, что при 45⁰ площадь может быть больше.
Можно подкорректировать.

Но уже тогда я учитывал, что прямоугольник можно не поворачивать (если он изначально полностью помещается внутри квадрата и прочие частные случаи).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  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

В конце тогда можно просто выводить InnerRectSquare (если до него дело доходит после проверок) и "забить" на RectSquare.

@KSergey9 · 14.06.2023, 14:50

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

Плюс из серии "критикуешь - предлагай".

С добрым утром!
Я ж написал: ни шмагла.

Где вы увидели критику - даже и не знаю.

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

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

@Royal_X · 14.06.2023, 14:56

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

смысла возиться с такой задачей нет никакого, к программированию она отношения не имеет

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

@KSergey9 · 14.06.2023, 15:02

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

программирование тесно связано с математикой.

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

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

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

А поделитесь разными алгоритмами, плиз? идеями достаточно. Для понимания о чем речь, ибо у меня только 2 идеи.

@gunslinger · 14.06.2023, 15:08

KSergey9, мне казалось, что камни летят в мой огород. Хоть это не принципиально.
Насчет "темы рядом" - я и (код в стиле) ООП не совместимы с рождения (когда учился в ~~ПТУ~~ ВУЗе, ООП не особо понимал, в итоге так и не наверстал).

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

@Royal_X · 14.06.2023, 15:14

KSergey9, ну вот самый правильный и точный алгоритм - это если будем всё считать по формулам.
Но есть и ленивый метод - вычисление площади методом Монте-Карло: бросаем на квадрат рандомные точки. Площадь покрытой части тогда будет равна s = S * m / n, где S это площадь квадрата, m это точки которые попали в прямоугольник, n количество точек, брошенных в квадрат. Чем больше будет n, тем точнее результат. Всё это реализуется достаточно просто. Нужно всего лишь написать bool функцию, которая проверяет попадает ли точка в прямоугольник, и если попадает, то ++m.

@KSergey9 · 14.06.2023, 15:17

Не по теме:

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

ООП не совместимы с рождения

А что там можно не понимать?
Спросите (в новой теме?), наверняка растолкуют.
Боюсь, что вы слишком себя ограничиваете этим, тем более в рамках С++
Ну если это профессия, а не вспомогательные навыки на фоне основной деятельности.

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

условие задачи "максимальная сторона прямоугольника должна быть меньше диагонали квадрата" вполне можно свести к условию "...должна быть не больше...". Почему там равенства быть не должно - не понимаю.

Вам не понятно условие задачи и текст в нём, или не понятная чья-то реплика на это счёт?
Или код в приведенной мною программе?

Добавлено через 1 минуту
Royal_X, но это как раз те самые 2 идеи, которые есть у меня.
(только вместо Монте-Карло я реализовал полный перебор по сетке)

А еще?

@gunslinger · 14.06.2023, 15:18

KSergey9, программирование - это не моя профессия (уже давно).

По условию задачи - это просто мысли вслух.

@Royal_X · 14.06.2023, 15:35

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

Почему там равенства быть не должно - не понимаю.

Потому что условие писал идиот

какая разница, у меня максимальная сторона прямоугольника a * sqrt(2) или a * sqrt(2) - 1e-100.
А еще лучше, если максимальная сторона прямоугольника a * sqrt(2) - геометрическая точка.

Добавлено через 11 минут

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

А еще?

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

@gunslinger · 14.06.2023, 15:40

Кстати, если макс. сторона прямоугольника будет больше диагонали квадрата, то, кроме "других формул" расчета площади, может (теоретически, но это не точно) перестать работать "идея" про 45⁰. Однако тут уже другая история.

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

А еще лучше, если максимальная сторона прямоугольника a * sqrt(2) - геометрическая точка.

Что здесь подразумевается под "геометрической точкой"? Не очень понимаю.

@KSergey9 · 14.06.2023, 15:44

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

если макс. сторона будет больше диагонали квадрата,
может (теоретически, но это не точно) перестать работать "идея" про 450. Однако тут уже другая история.

Не, всё равно 45, проверял

@Royal_X · 14.06.2023, 15:54

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

Что здесь подразумевается под "геометрической точкой"?

В геометрии точка это фундаментальный объект. Например, толщина окружности это точка, ибо окружность по сути это множество точек, равноудалённых от некой заданной точки. Или вот, например, радиус открытого и закрытого круга отличается на одну геометрическую точку.

Добавлено через 7 минут

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

Не, всё равно 45, проверял

Вспомнил одну задачку на смекалку на эту тему.

Некто хочет перевезти в автобусе трубу длиной 2,5 м. Но в автобусе разрешено перевезти вещи, габариты (длина, ширина или высота) которых не превышают 2 м. Как ему решить данную проблему?

@KSergey9 · 14.06.2023, 15:57

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

Как ему решить данную проблему?

На крыше!

Новые блоги и статьи Все статьи Все блоги /
Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .	Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.	Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))
Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .	Своя Интернет-Компания iceja 18.06.2026 Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .	24 Мат модель здравосохранения: функциональные требования к строительству пищеблока anaschu 18.06.2026 СРесурсами1: финансовый SD-контур, калькулятор функциональных требований пищеблока Сегодня разделили затраты в агенте Экономика по образцу модели НАСОСЫ, добавили расчёт ROI и построили первый. . .	23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .

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

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

@Royal_X 6289 / 3013 / 1051 Регистрация: 01.06.2021 Сообщений: 11,327
	14.06.2023, 14:29
	gunslinger, но ведь не всегда угол 45 градусов дает макс площадь. Например, если стороны прямоугольника равны стороне квадрата, то лучше не поворачивать: 1

@Royal_X 6289 / 3013 / 1051 Регистрация: 01.06.2021 Сообщений: 11,327
	14.06.2023, 14:39
	gunslinger, т.е. ты считаешь и при 0° и при 45°, но выводишь ту площадь, что больше? 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,026
	14.06.2023, 15:08
	KSergey9, мне казалось, что камни летят в мой огород. Хоть это не принципиально. Насчет "темы рядом" - я и (код в стиле) ООП не совместимы с рождения (когда учился в ~~ПТУ~~ ВУЗе, ООП не особо понимал, в итоге так и не наверстал). Пока не забыл, условие задачи "максимальная сторона прямоугольника должна быть меньше диагонали квадрата" вполне можно свести к условию "...должна быть не больше...". Почему там равенства быть не должно - не понимаю. Почему не должно быть больше - понятно, расчет площади от этого изменится, так как меньшие стороны прямоугольника могут (и будут) в какой-то момент поворота выходить за углы квадрата. 0

@Royal_X 6289 / 3013 / 1051 Регистрация: 01.06.2021 Сообщений: 11,327
	14.06.2023, 15:14
	KSergey9, ну вот самый правильный и точный алгоритм - это если будем всё считать по формулам. Но есть и ленивый метод - вычисление площади методом Монте-Карло: бросаем на квадрат рандомные точки. Площадь покрытой части тогда будет равна `s = S * m / n`, где S это площадь квадрата, m это точки которые попали в прямоугольник, n количество точек, брошенных в квадрат. Чем больше будет n, тем точнее результат. Всё это реализуется достаточно просто. Нужно всего лишь написать bool функцию, которая проверяет попадает ли точка в прямоугольник, и если попадает, то ++m. 1

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,026
	14.06.2023, 15:18
	KSergey9, программирование - это не моя профессия (уже давно). По условию задачи - это просто мысли вслух. 0