Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: поиск максимальной площади треугольника  (Прочитано 16189 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 01-10-2009 16:35 » 

даны квадраты 2х сторон треугольника

нужно при условии, что первая вершина расположена в 0,0 достроить 2ю и 3ю вершины так, чтобы площадь получившегося треугольника была максимальной и координаты вершин являлись целыми числами

и вывести получившуюся площадь, либо -1 когда такого треугольника не существует
« Последнее редактирование: 01-10-2009 18:52 от Вад » Записан

1n c0de we trust
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #1 : 01-10-2009 18:49 » new

Ну и?
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Finch
Спокойный
Администратор

il
Online Online
Пол: Мужской
Пролетал мимо


« Ответ #2 : 01-10-2009 19:49 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 01-10-2009 20:14 » 

Открываем википедию, смотрим там формулы площади треугольника, выбираем нужную. Площадь равна половине произведения двух сторон на синус угла между ними. Задача сводится к максимизации синуса угла. Синус достигает максимума при 90 градусах. Надеюсь, понятно, что это значит Улыбаюсь
Записан
sss
Специалист

ru
Offline Offline

« Ответ #4 : 02-10-2009 01:18 » 

Дано:
  a*a, b*b - длины сторон

Решение:
  v0 = (0 ; 0)
  v1 = (a ; 0)
  v2 = (a ; b)

P.S.: Да, забыл... Решения нет, если a или b не целое число...
« Последнее редактирование: 02-10-2009 01:23 от sss » Записан

while (8==8)
Mayor
Специалист

ru
Offline Offline

« Ответ #5 : 02-10-2009 11:23 » 

P.S.: Да, забыл... Решения нет, если a или b не целое число...

не совсем, возьми к примеру 85 и 41, для них есть решение >=26.5, несмотря на то, что корни из 41 и 85 не целые числа

дано a=85 и b=41 или наоборот  

решения нет если не принадлежат целым x1,y1 или x2,y2, такие что
(x1+y1)^2==a//9+2
(x2+y2)^2==b//4+5

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

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

зы забыл упомянуть, нужно чтобы решение выдавалось за 2 секунды

те первую попавшуюся сторону я найду за Omax(sqrt(a)/2), что при а типа int составит около 32678 переборов, вторую найду за столько же, в принципе я даже наверное найду все возможные координаты сторон за 131072 итераций

но я завис над алгоритмом который за линейное время выберет из этих сторон комбинацию с углом между ними == или максимально приближенным к 90 градусам

зыы только что нашел для 41 и 85 более правильное решение: 4;5 & 6;7
« Последнее редактирование: 02-10-2009 11:29 от Mayor » Записан

1n c0de we trust
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 02-10-2009 12:24 » 

давайте рассмотрим задачу
Цитата
даны квадраты 2х сторон треугольника

нужно при условии, что первая вершина расположена в 0,0 достроить 2ю и 3ю вершины так, чтобы площадь получившегося треугольника была максимальной и координаты вершин являлись целыми числами

Учитывая что координаты вершин являлись целыми числами, можно сделать вывод, что длины сторон не обязательно должны быть целыми.
1. Необходимо найти координаты стороны a, чтоб удовлетворяли условию.
2. Необходимо найти координаты стороны b, чтоб удовлетворяли условию.

А это сводится к решению квадратных уравнений.

И привязываться к прямому углу, не совсем обязательно.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines