IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> задачка на геометрию, очень сложная по моему
сообщение
Сообщение #1


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


У меня тут одна задачка появилась , никак не могу решить mega_chok.gif .Она тоже с acm.timus.ru. У меня несколько(т.е. 12) тестов проходит nea.gif . Спрашивал у всех учителей математики нашей школы. Каждый говорит одно, но никакой из тех алго не проходит. norespect.gif Самый лучший пока мой собственный cool.gif .

Ну в задаче, если коротко описать, нужно определить можно ли поместить второй треугольник в первый. Длина сторон каждого заданы. Мой алгоритм не очень уж и трудный. Я сначала нахожу сторону с макс. длиной и беру его как за основание(это действие выполняю для обоих). Потом сраниваю основания и вершины(по основанию) и выдаю ответ. Вот и мой код:

var
k,l1,l2,a,b,c,x,y,z:longint;
h1,h2,p1,p2:extended;

function max(x,y,z:longint):longint;
begin
if (x>=y)and(x>=z) then max:=x
else
if (y>=z)and(y>=x) then max:=y
else max:=z;
end;

procedure smen(var a,b,c:longint; l:longint);
begin
if a=l then
begin
k:=c;
c:=a;
a:=k;
end else
if b=l then
begin
k:=c;
c:=b;
b:=k;
end;
end;

begin
readln(x,y,z);
readln(a,b,c);
p2:=(a+b+c)/2;
p1:=(x+y+z)/2;
l1:=max(x,y,z);
l2:=max(a,b,c);
smen(x,y,z,l1);
h1:=(2/z)*sqrt(p1*(p1-x)*(p1-y)*(p1-z));
hx:=(2/x)*sqrt(p1*(p1-x)*(p1-y)*(p1-z));
hy:=(2/y)*sqrt(p1*(p1-x)*(p1-y)*(p1-z));
smen(a,b,c,l2);
h2:=(2/c)*sqrt(p2*(p2-a)*(p2-b)*(p2-c));
ha:=(2/a)*sqrt(p2*(p2-a)*(p2-b)*(p2-c));
hb:=(2/b)*sqrt(p2*(p2-a)*(p2-b)*(p2-c));
if not ((l1>=l2)and(h1>=h2)) then writeln('NO')
else writeln('YES');
end.



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

Недаюь сможете помочь. Заранее спасибо... smile.gif


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 731
Пол: Женский

Репутация: -  25  +


Цитата
если основание и высота первого больше но второй треугольник не входит

т.е. примерно так выглядят треугольники:
Прикрепленное изображение
Может тогда нужно все высоты сравнивать на больше меньше (посмотри на их длины на рисунке).. Но не уверена, ибо с геометрией у меня туго..

p.s. так вот для чего была нужна формула))) [offtop] а кто-нибудь кроме меня когда-нибудь проверял перпендикулярность, прикладыванием чего-нибудь прямоугольного к экрану? blink.gif [/offtop]

Сообщение отредактировано: Айра -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Полное решение этой задачи - очень, очень сложное. Честное слово smile.gif

Ну не то чтобы очень сложное, но очень громоздкое.

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



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


Я - нет. Зато я пытался проводить ровную линию карандашом в MS Paint'e, проводя мышкой вдоль края учебника.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Цитата
p.s. так вот для чего была нужна формула)))

да именно для этой задачи yes2.gif

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

И это пробовал не помогает. Кстати у меня в проге остались следы(я нашел высоты других сторон но не использовал mega_chok.gif )...

Цитата
Полное решение этой задачи - очень, очень сложное. Честное слово .Ну не то чтобы очень сложное, но очень громоздкое.


Ну про сложность я потом узнал. Всего 30 людей решили примерно 5% norespect.gif . Это конечно же очень мало. Ну просто захотелось стать одним из них. И щас хочу rolleyes.gif

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


Нет не могу. Просто это было первое что пришло мне в голову. Но помоему если доработать мою программу то может и получиться wink.gif . Ведь я же знаю где у меня ошибка(ну я не говорю что она единственная:wacko:...)
Кстати да решение всегда существует или входит или нет lol.gif


P.S. Ну хотя бы можете подсказать как мне исправить ту ошибку blum.gif


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ну ок, давай попробуем.

А = тот треугольник, ВНУТРЬ которого вставляем, В - ТОТ, который вставляем.

ВВВ = Верхняя Вершина треугольника В

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

Получается, нужно найти на левой боковой стороне А точку Х с нужной нам ординатой (с ординатой ВВВ), и попробовать поставить В там (совместить ВВВ с Х). Если теперь мы вылезли за пределы А справа (основание В вылезло вправо от основания А) - решения точно нет. Если не вылезли - решение найдено.

Bard, если ты действительно хочешь сдать эту задачу, я бы советовал тебе сначала порешать другую геометрию на тимусе. Можешь искать ее по ключевым словам "coordinate", "vertex", "circle", "intersect" и т. п.

Например: По запросу coordinate|circle|intersect|triangle +site:acm.timus.ru

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Слушайте, а если обойтись простой логикой?
Если основание1 первого треугольника больше основания второго треугольника, то можно проверять дальше.
Если левое ребро первого треугольника больше левого ребра второго треугольника и
правое ребро первого треугольника больше правого ребра второго треугольника, то второй треугольник можно поместить внутрь первого.

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


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Если левое ребро первого треугольника больше левого ребра второго треугольника и
правое ребро первого треугольника больше правого ребра второго треугольника, то второй треугольник можно поместить внутрь первого.

Отлично. Теперь придумай контрпример для своего утверждения ;) Оно ошибочно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Цитата(Michael_Rybak @ 14.01.2008 18:40) *

Отлично. Теперь придумай контрпример для своего утверждения ;) Оно ошибочно.

Какой пример? Назови стороны двух треугольников.


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Нет, это ты назови стороны двух треугольников. Подумай, и назови сам smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Цитата(Michael_Rybak @ 14.01.2008 20:47) *

Нет, это ты назови стороны двух треугольников. Подумай, и назови сам smile.gif

Слушай, ну мы так ещё долго отписываться будем. Что ты имеешь в виду. Я не вижу там проколов, если видишь назови цифры.


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Слушай, ну мы так ещё долго отписываться будем.

Я не спешу smile.gif И автору твое сообщение не поможет. Он использует более слабый факт без доказательства, и то безуспешно.

Цитата
если видишь назови цифры.

Вижу. Не назову. Зачем? Так неинтересно smile.gif Где прокол - я тебе сказал. В утверждении, что из того, что каждая сторона одного треугольника меньше соответствующей стороны другого следует, что первый можно вложить во второй.

Это утверждение нельзя использовать просто так. Его нужно доказать. Или опровергнуть.

Цитата
Я не вижу там проколов

В таком случае докажи правильность своего решения.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Ладно, сам уже нашёл. Написал бы цифры было проще.


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Написал бы цифры было проще.

Конечно. А если бы сдал за автора задачу на тимусе, было бы еще проще. И?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Профи
****

Группа: Пользователи
Сообщений: 731
Пол: Женский

Репутация: -  25  +


А можно мне пример? 10.gif
Кстати, а треугольники нельзя поворачивать\переворачивать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
А можно мне пример?


И тебе нельзя! :D

Ну если правда хочешь, то можно. Но лучше сама.

Спойлер (Показать/Скрыть)


Цитата
Кстати, а треугольники нельзя поворачивать\переворачивать?

Молодец, отличный вопрос (именно про переворачивать).

Можно. Мы вкладываем треугольное письмо в треугольный конверт (см. ссылку на тимус).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Профи
****

Группа: Пользователи
Сообщений: 731
Пол: Женский

Репутация: -  25  +


Цитата
Если теперь мы вылезли за пределы А справа (основание В вылезло вправо от основания А) - решения точно нет

Получается тут можно попробовать как бы зеркально отобразить наш треугольник В и проделать те же махинации?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Получается тут можно попробовать как бы зеркально отобразить наш треугольник В и проделать те же махинации?

Угу.

На самом деле достаточно написать одну процедуру Check(a1, b1, c1, a2, b2, c2), и потом вызвать ее шесть раз:

Check(a1, b1, c1, a2, b2, c2)
Check(a1, b1, c1, a2, c2, b2)
Check(a1, b1, c1, b2, a2, c2)
Check(a1, b1, c1, b2, c2, a2)
Check(a1, b1, c1, c2, a2, b2)
Check(a1, b1, c1, c2, b2, a2)

В этих вызовах мы перебираем, какая сторона будет какой соответствовать; и внутри процедуры это соответствие считаем уже фиксированным.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Цитата
Я не спешу smile.gif И автору твое сообщение не поможет. Он использует более слабый факт без доказательства, и то безуспешно.


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

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


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

Цитата
А можно мне пример?


ну вот тебе допустим такой неординарный пример который доказывает ошибочность алго feniks25.
1000 510 510
900 900 1

ответ: да, входит. если положить сторону с длиной 900 на сторону дл. 1000 то можно все увидеть.
лучше будет начертить тогда сама все поймешь


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Цитата(Bard @ 15.01.2008 0:03) *

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

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

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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


Цитата
На самом деле достаточно написать одну процедуру Check(a1, b1, c1, a2, b2, c2)
Т.е. отсортировать по величинам длин сторон? так что бы наибольшая стала основанием,2-я
по величине слева, 3-я справа.Тогда, как я понял, будет как на риснке (см ниже)? если так,
то просто остается сравнивать. Вроде этот вариант подходит ко всем треугольникам


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:20
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name