Помощь - Поиск - Пользователи - Календарь
Полная версия: задачка на геометрию
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
У меня тут одна задачка появилась , никак не могу решить 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
Айра
Цитата
если основание и высота первого больше но второй треугольник не входит

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

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

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

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



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


Я - нет. Зато я пытался проводить ровную линию карандашом в MS Paint'e, проводя мышкой вдоль края учебника.
Bard
Цитата
p.s. так вот для чего была нужна формула)))

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

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

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

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


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

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


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


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

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

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

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

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

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

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

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

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

Отлично. Теперь придумай контрпример для своего утверждения ;) Оно ошибочно.
Rian
Цитата(Michael_Rybak @ 14.01.2008 18:40) *

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

Какой пример? Назови стороны двух треугольников.
Michael_Rybak
Нет, это ты назови стороны двух треугольников. Подумай, и назови сам smile.gif
Rian
Цитата(Michael_Rybak @ 14.01.2008 20:47) *

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

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

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

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

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

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

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

В таком случае докажи правильность своего решения.
Rian
Ладно, сам уже нашёл. Написал бы цифры было проще.
Michael_Rybak
Цитата
Написал бы цифры было проще.

Конечно. А если бы сдал за автора задачу на тимусе, было бы еще проще. И?
Айра
А можно мне пример? 10.gif
Кстати, а треугольники нельзя поворачивать\переворачивать?
Michael_Rybak
Цитата
А можно мне пример?


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

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

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


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

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

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

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

Угу.

На самом деле достаточно написать одну процедуру 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)

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


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

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


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

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


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

ответ: да, входит. если положить сторону с длиной 900 на сторону дл. 1000 то можно все увидеть.
лучше будет начертить тогда сама все поймешь
Rian
Цитата(Bard @ 15.01.2008 0:03) *

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

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

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

Ну попробуй. По-моему - нельзя.

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

Да. Но вариантов всего 6, потому полный перебор - это и есть те шесть вызовов.

Цитата
Т.е. отсортировать по величинам длин сторон? так что бы наибольшая стала основанием,2-я
по величине слева, 3-я справа.

Нет. Не отсортировать, а установить попарное соответствие.
Rian
Цитата(Client @ 15.01.2008 9:39) *

Т.е. отсортировать по величинам длин сторон?


Нет, ну не получается привязываться к длинам напрямую.
рис...
Все стороны красного меньше, а как не крути не влезет sad.gif

smile.gif сказал "смотри на рисунок", а из головы выложить забыл.
Айра
Цитата
Все стороны красного меньше

Про высоту не забываем))
Гость
Цитата(Айра @ 15.01.2008 13:10) *

Про высоту не забываем))

Ну а высота то, что нам даст? Подними левую точку чёрного треугольника на 1 и условие опять рассыпится
Айра
Поднимаем левую точку на 1-цу -> высоты становятся равными. Затем переворачиваем красный треугольник: кладем его основанием на основание (то бишь самую длинную сторону) черного и совмещаем вершины, что напротив оснований, и о, чудо! Он поместился! smile.gif
Rian
Цитата(Айра @ 15.01.2008 18:58) *

совмещаем вершины, что напротив оснований, и о, чудо! Он поместился! smile.gif

Слушай, а может и правда будет работать
Michael_Rybak
Тогда можно основание черного уменьшить вдвое (подвинуть левую вершину до середины основания). И опять не влезет.

Что за гадания, ребята. Может, не может. Надо доказывать.
Bard
Цитата
Что за гадания, ребята. Может, не может. Надо доказывать.

Абсолютно согласен. Нам нужно найти такой алгоритм чтобы он работал для любых случаев.

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

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

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

А как можно определить на какие точки, в координатной плоскости, попадают вершины , если нам заданы только длины сторон треугольников?
Rian
Цитата(Bard @ 16.01.2008 18:51) *

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


Нужно рассчитать углы между сторонами. Потом декартовы координаты из полярных.
Основание можно сильно не считать, оно параллельно оси Х

Формулы в файле.
Bard
Всем привет... Огромное спасибо всем кто принял активное участие в решении этой задачи. Я наконец-то смог ее решить. Вот и ее решение на паскале.

USES Math;
Var a,b,c:extended;
ca,cb,cc,ha,hb,hc:extended;
a1,b1,c1:extended;
ca1,cb1,cc1,ha1,hb1,hc1:extended;
{.........................................................}
Procedure TRI(a,b,c:extended;Var CA,CB,CC,ha,hb,hc:extended);
Var
S,p:extended;
begin
p:=(a+b+c)/2;
S:=sqrt(p*(p-a)*(p-b)*(p-c));
ha:=2*s/a; hb:=2*s/b; hc:=2*s/c;
CC:=arcsin(ha/b); CB:=arcsin(ha/C); CA:=arcsin(hc/b);
if (c*c>a*a+b*b) then CC:=pi-CC else
if (b*b>a*a+c*c) then CB:=pi-CB else
if (a*a>c*c+b*b) then CA:=pi-CA;
end;
{}{}{}{}{}{}{}{}{}{}{}{}
Function Konvert:Boolean;
Var
b2,c2,d:extended;
begin
if (a1>a) OR (ha1>ha) then Konvert:=false
else
if (CC1<=CC) and (CB1<=CB) then Konvert:=true
else
if (CC1>CC) then
begin
b2:=ha1/sin(CC);
d:=sqrt(b2*b2+b1*b1-2*b1*b2*cos(CC1-CC));
if d+a1>a then Konvert:=false
else Konvert:=true;
end
else
if (CB1>CB) then
begin
c2:=ha1/sin(CB);
d:=sqrt(c2*c2+c1*c1-2*c1*c2*cos(CB1-CB));
if d+a1>a then Konvert:=false
else Konvert:=true;

end;

end;
{******************}
Procedure Sdvig(Var a,b,c,CA,CB,CC,ha,hb,hc:extended);
Var
x,y:extended;
begin
y:=b; b:=a; a:=c; c:=y;
x:=hb; hb:=ha; ha:=hc; hc:=x;
x:=cb; cb:=ca; ca:=cc; cc:=x;
end;
{------------------------}
Procedure Perev;
Var x,y:extended;
begin
y:=b1; b1:=c1; c1:=y;
x:=CC1; CC1:=CB1; CB1:=x;
x:=hC1; hC1:=hB1; hB1:=x;
end;
{=====================================}
Var i,j:integer; p:Boolean;
BEGIN
readln(a,b,c); readln(a1,b1,c1); p:=false;

TRI(a,b,c,ca,cb,cc,ha,hb,hc);
TRI(a1,b1,c1,ca1,cb1,cc1,ha1,hb1,hc1);

for
i:=1 to 3 do
begin
for j:=1 to 3 do
begin
if Konvert then begin p:=true; break; end;
Perev;
if Konvert then begin p:=true; break; end;
Perev;
Sdvig(a1,b1,c1,CA1,CB1,CC1,ha1,hb1,hc1);
end;
if p then break;
Sdvig(a,b,c,CA,CB,CC,ha,hb,hc);
end;

if p then writeln('YES') else writeln('NO');
END.


Ну надеюсь алго вы сами поймете good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.