Форум программистов, компьютерный форум CyberForum.ru

Определение максимальной площади - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.86
alex_bojik
Заблокирован
02.11.2011, 11:00     Определение максимальной площади #1
Доброго все времени суток!
Есть 2 луча исходящие из одной точки, угол между ними 90. Есть также 2 отрезка a и b. Необходимо найти такое расположение этих отрезков, чтобы получился четырехугольник максимальной площади... причем положения находить необязательно достаточно вычислить площадь...
Задача взята отсюда
Если кто знает какие-нибудь теоремы на эту тему подскажите пожалста.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <math.h>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int a,b;
    double max = 0,max1 = 0,PI = 3.141592653589793238462643383;
    cin>>a>>b;
    for(int i=0;i<=180;i++)
        for(int j=0;j<=180;j++)
        {
            double x=a*sin(i*PI/360);
            double y=b*sin(j*PI/360);
            double s= (2*x*y+sqrt(a*a-x*x)*x+sqrt(b*b-y*y)*y)/2;
            if (max<s)
                max=s;
        }
    cout<<setprecision(7)<<fixed<<max;
    return 0;
}
Это примерное решение... но так как перебором не совсем точно
Есть идея по поводу производной от функции площади... но там две переменные и с этим небольшие проблемы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2011, 11:00     Определение максимальной площади
Посмотрите здесь:

C++ определить треугольники минимальной и максимальной площади, которые можно построить из этих отрезков
Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков C++
C++ Определение максимальной и минимальной цифры натурального числа
C++ Поиск максимальной компоненты файла
C++ Найдите треугольник максимальной площади
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
02.11.2011, 15:52     Определение максимальной площади #2
Думаю так, но могу ошибаться:

Определение максимальной площади

Почему-то мне кажется, что я ошибаюсь. Не может же оно быть так просто
alex_bojik
Заблокирован
02.11.2011, 16:08  [ТС]     Определение максимальной площади #3
Название: 123.png
Просмотров: 152

Размер: 1.7 Кб вот так примерно
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 17:06     Определение максимальной площади #4
площадь многоугольника максимальна, если его возможно вписать в окружность.
в случае четырехугольника, описать вокруг него окружность можно, если выполняется условие "произведение диагоналей = сумме произведений противоположных сторон".

пища для размышлений дана)
alex_bojik
Заблокирован
02.11.2011, 17:18  [ТС]     Определение максимальной площади #5
спасибо буду думать))))
Апострофф
Заблокирован
02.11.2011, 17:30     Определение максимальной площади #6
А мне что-то подсказывает, что решение где-то тут
Изображения
 
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 17:31     Определение максимальной площади #7
забыл указать, что это справедливо для выпуклого многоугольника. хотя сомневаюсь, что не выпуклый сможет оказаться больше по площади...
Апострофф
Заблокирован
02.11.2011, 17:42     Определение максимальной площади #8
Цитата Сообщение от Paporotnik Посмотреть сообщение
площадь многоугольника максимальна, если его возможно вписать в окружность
Это справедливо для случая, когда известны длины всех сторон, а не половины
alex_bojik
Заблокирован
02.11.2011, 17:45  [ТС]     Определение максимальной площади #9
Цитата Сообщение от Апострофф Посмотреть сообщение
А мне что-то подсказывает, что решение где-то тут
кстати я тоже так думал... но когда формулу выводил не получилось, хотя надо еще раз попробовать....

Добавлено через 1 минуту
Цитата Сообщение от Paporotnik Посмотреть сообщение
площадь многоугольника максимальна, если его возможно вписать в окружность
да кстати... в случае a = b получается что квадрат можно вписать в окружность... но его площадь не максимальна
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
02.11.2011, 17:52     Определение максимальной площади #10
Аж самому интересно стало. Развивая высказанную мысль:

Определение максимальной площади

Хотя, опять могу не туда смотреть
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 18:43     Определение максимальной площади #11
Это справедливо для случая, когда известны длины всех сторон, а не половины
это справедливо для любого выпуклого многоугольника. и не важно, что мы о нем знаем.

да кстати... в случае a = b получается что квадрат можно вписать в окружность... но его площадь не максимальна
в случае a=b получается, что a=b и только) это не дает никакой информации о двух других сторонах. это может быть и просто прямоугольный треугольник, и квадрат, и композиция прямоугольного треугольника и равнобедренного треугольника с основанием на диагонали.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 18:52     Определение максимальной площади #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
в общем поразмышлял.
если многоугольник можно вписать в окружность, то он имеет максимальную площадь.
представим, что этот многоугольник у нас 8-угольный. причем обладает горизонтальной и вертикальной симметрией, т.е. состоит из 4-х одинаковых 4-х угольников.
совершенно очевидно, что если весь многоугольник имеет максимальную площадь, то и каждый из этих 4-х угольников будет иметь максимальную площадь.
таким образом, имеем 4-х угольник (к примеру, возьмем тот, что оказывается в 1-ой четверти описанной окружности), одна вершина которого находится в центре описанной окружности, две других смежных вершины - соответственно справа и сверху от нее на расстоянии R, а четвертая - где-то на дуге, отсеченной образованным прямым углом.
получается, что искомая площадь получится как сумма двух равнобедренных треугольников, причем "бедра" обоих равны радиусу, а основание известно из условия.
доводить до формулы лень. возможно понадобится тот факт, что радиус, перпендикулярный хорде, делит ее пополам.

картинка, для понимания)
Миниатюры
Определение максимальной площади  
Cute
 Аватар для Cute
1061 / 643 / 66
Регистрация: 10.02.2011
Сообщений: 518
02.11.2011, 21:11     Определение максимальной площади #13
Данную задачу можно решить, используя метод оценок.
Миниатюры
Определение максимальной площади   Определение максимальной площади  
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 22:09     Определение максимальной площади #14
а по-моему твоя формула показывает площадь композиции равнобедренного и прямоугольного треугольника. и это не связано с максимальной площадью получаемой фигуры.

с чего ты взял, что максимальная площадь будет стремиться к сумме равнобедренного ABC и прямоугольного BCD?
тебе не кажется, что достаточно точку B перенести выше (зеркально отразить относительно горизонтали через D) и площадь фигуры увеличится значительно, а твоя формула будет по-прежнему указывать на площадь старой фигуры?

p.s. в вычислениях по-прежнему много ошибок)
Cute
 Аватар для Cute
1061 / 643 / 66
Регистрация: 10.02.2011
Сообщений: 518
02.11.2011, 22:50     Определение максимальной площади #15
Ошибки я заметил и исправил (сегодня я очень рассеянный). Ниже выложу исправленный вариант.

Моё решение основано на следующих фактах.

1) Площадь четырёхугольника ABCD равна сумме площадей его частей - треугольников BDA и BDC (свойство аддитивности площади). Если каждое из слагаемых будет максимально возможным, то и суммарная площадь будет максимальной.

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

Далее из всех треугольников со сторонами a, b и углом между ними gamma наибольшую площадь будет иметь прямоугольный треугольник с катетами a, b и углом gamma=90 градусов.

Если в моих рассуждениях есть ошибки, то укажите их.
Миниатюры
Определение максимальной площади   Определение максимальной площади  
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
02.11.2011, 23:10     Определение максимальной площади #16
Предположим, что четырёхугольник ABCD максимальной площади уже построен, тогда прямоугольный треугольник BDA должен являться равнобедренным, так как из всех прямоугольных треугольников с данной гипотенузой наибольшую площадь имеет равнобедренный.
совершенно верно, но с чего ты взял, что в построенном ABCD второй прямоугольник окажется именно прямоугольным?

итак, BAD равнобедренный прямоугольный, без сомнения. его площадь можно выразить через гипотенузу, что ты и сделал в своих рассчетах, S=d^2/4.
треугольник BCD ты считаешь прямоугольным, а значит S=a*b/2. Замечу, что эта формула ТОЛЬКО для прямоугольных.
выражая d через a и b и записывая сумму площадей получаем: (a^2+b^2)/4+a*b/2=(a+b)^2/4.
Получаем твою формулу. т.е. она справедлива ТОЛЬКО для композиции двух прямоугольных треугольников, один из которых равнобедренный.

а теперь делаем простой фокус, не нарушая условие. и получаем гораздо большую площадь. она не максимальная, но уже больше той, что получается по твоей формуле.
Миниатюры
Определение максимальной площади  
alex_bojik
Заблокирован
02.11.2011, 23:16  [ТС]     Определение максимальной площади #17
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ну что я могу сказать))) задача решена всем кто помогал огромное спасибо и конечно же +
talis - спасибо за попытки помочь!
Апострофф - спасибо, что помогли еще раз взглянуть с этой позиции, и найти правильный ответ
Cute - спасибо за ваши старания, очень все понятно и доступно!
Paporotnik - спасибо за доказательство насчет 8-угольника, и вообще за помощь!

Решение математически:
Определение максимальной площади

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{\Delta BCD}=\frac{1}{2}\cdot a\cdot b\cdot \sin \gamma = \frac{\sqrt{2}}{2}\cdot a\cdot b
http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{\Delta ABD}=\frac{1}{2}\cdot {r}^{2}
http://www.cyberforum.ru/cgi-bin/latex.cgi?2\cdot {r}^{2}={c}^{2}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{\Delta ABD}=\frac{1}{4}\cdot {c}^{2}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{c}^{2}={a}^{2} + {b}^{2} - 2\cdot a\cdot b\cdot \cos \gamma
http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{ABCD}=\frac{{a}^{2}+{b}^{2}}{4}+\frac{\sqrt{2}}{2}\cdot a\cdot b

Решение C++
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <math.h>
#include <iomanip>
 
using namespace std;
 
int main()
{
    double a,b;
    double max = 0;
    cin>>a>>b;
    max = (a*a+b*b)/4+sqrt(2)*a*b/2;
    cout<<setprecision(7)<<fixed<<max;
    return 0;
}
alex_bojik
Заблокирован
02.11.2011, 23:22  [ТС]     Определение максимальной площади #18
ах да, а как отметить что проблема решена?
не в смысле отпраздновать, а замочек повесить... или как тут вообще делается
Cute
 Аватар для Cute
1061 / 643 / 66
Регистрация: 10.02.2011
Сообщений: 518
03.11.2011, 00:01     Определение максимальной площади #19
Цитата Сообщение от alex_bojik Посмотреть сообщение
ах да, а как отметить что проблема решена?
не в смысле отпраздновать, а замочек повесить... или как тут вообще делается
Рано-рано ещё закрывать тему, alex_bojik.

При расчёте площади треугольника BCD вы считаете, что sin(gamma)=sqrt(2).
Но sqrt(2)>1. А синус любого угла не может быть больше единицы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2011, 00:13     Определение максимальной площади
Еще ссылки по теме:

C++ Определение максимальной и минимальной суммы двух соседних элементов массива
C++ Подсветить предложение максимальной длины
C++ N треугольников плоскости заданы длинами своих сторон. Найдите треугольник максимальной площади

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

Или воспользуйтесь поиском по форуму:
alex_bojik
Заблокирован
03.11.2011, 00:13  [ТС]     Определение максимальной площади #20
там sqrt(2)/2 просто упрощение долго в LaTex набирать
Yandex
Объявления
03.11.2011, 00:13     Определение максимальной площади
Ответ Создать тему
Опции темы

Текущее время: 10:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru