Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 53
Мораль сей публикации такова, что надо сначала подумать, а затем решать. Какого, извиняюсь, лешего, Вы зеркало описываете прямой ax+b?
Школьники поумнее заменят уравнение зеркала на x=0 и все Ваши зубодробительные формулы превратятся в тыкву. И никаких попиндикуляров искать не надо.
Впрочем, я могу ошибаться, но это вряд ли.
Школьники поумнее заменят уравнение зеркала на x=0 и все Ваши зубодробительные формулы превратятся в тыкву. И никаких попиндикуляров искать не надо.
Впрочем, я могу ошибаться, но это вряд ли.
Возможно, но тут две вещи.
1. Не забывайте, перед нами школьники. Аналитическая геометрия — это, извините, 1-й курс вуза. В школе стоит обходиться только «интуитивными» векторными формулами в 2D, которые легко переизобрести, вроде косого произведения векторов. И уж точно ничего не множить на матрицы и не раскладывать по базисам.
2. Второй источник сложности в том, что надо остаться в целой арифметике!
1. Не забывайте, перед нами школьники. Аналитическая геометрия — это, извините, 1-й курс вуза. В школе стоит обходиться только «интуитивными» векторными формулами в 2D, которые легко переизобрести, вроде косого произведения векторов. И уж точно ничего не множить на матрицы и не раскладывать по базисам.
2. Второй источник сложности в том, что надо остаться в целой арифметике!
P.S. Я и сам на украинской олимпиаде сталкивался с «забеганием вперёд». 8-й класс, хорошо решается через подобие (9 класс) и никак — если его не знаешь.
Я считаю, забегание вперёд — это плохо. Те, кого специально натаскивали, имеют преимущество перед теми, кто допёр сам.
Я считаю, забегание вперёд — это плохо. Те, кого специально натаскивали, имеют преимущество перед теми, кто допёр сам.
Что тут плохого — это что, контрольная работа, обязательная для всего класса? Нет. Это олимпиада — занятие добровольное, для самых умных и увлечённых предметом, предполагать у них наличие знаний вне базового курса «для троешников» — это нормально. И да, «специально натасканные» имеют преимущество перед неподготовленными, так же как это происходит в спорте, бизнесе, да и вообще в жизни. А что, должно быть иначе?
В технических дисциплинах нет необходимости выходить за пределы базового курса. Можно придумать придумать много интересных задач которые решаются неочевидной комбинацией простых методов (или очевидной комбинацией сложных).
Суть олимпиады стимулировать креативность и способность выходить за рамки программы. Иначе вместо того чтобы отбирать людей способных написать учебник за N+1 год, мы будем отбирать только тех кто всего-лишь прочитал учебник за N+1 год. А что делать когда мы доберемся до Nmax, кто будет изобретать Nmax+1?
Суть олимпиады стимулировать креативность и способность выходить за рамки программы. Иначе вместо того чтобы отбирать людей способных написать учебник за N+1 год, мы будем отбирать только тех кто всего-лишь прочитал учебник за N+1 год. А что делать когда мы доберемся до Nmax, кто будет изобретать Nmax+1?
«Специально натасканные» — это те, у кого есть профессиональный тренер, разбирающийся в специфике дела! Но бывают и другие варианты…
• тренер кто попало, со спецификой олимпиад малознакомый;
• вместо тренера — задачник. Хорошо, сейчас интернет; у меня по информатике был один покровитель за 100 км, от него с оказией что-нибудь да и приходило флоппинетом.
• тренер кто попало, со спецификой олимпиад малознакомый;
• вместо тренера — задачник. Хорошо, сейчас интернет; у меня по информатике был один покровитель за 100 км, от него с оказией что-нибудь да и приходило флоппинетом.
Согласен, возможно, я сам себе усложнил решение, когда ввел условие о целочисленном исчислении, но только это условие дает 100% верный результат; кто знает, но в вашем алгоритме если задать точку на границе зеркала она может не пройти…
и еще: во-первых, это усложнение заключается лишь в том, что нужно все хвосты (промежуточные вычисления) тащить за собой, а не просто сохранить в переменные.
во-вторых, ваше решение по объему выйдет не меньше чем мое, не так просто в математике уйти от сложности: попробуйте расписать свои пункты 1, 3 и 4 — вы получите те же несколько систем уравнений, но в довесок ко всему еще и несколько косинусов и арктангенсов (в п.1)
и еще: во-первых, это усложнение заключается лишь в том, что нужно все хвосты (промежуточные вычисления) тащить за собой, а не просто сохранить в переменные.
во-вторых, ваше решение по объему выйдет не меньше чем мое, не так просто в математике уйти от сложности: попробуйте расписать свои пункты 1, 3 и 4 — вы получите те же несколько систем уравнений, но в довесок ко всему еще и несколько косинусов и арктангенсов (в п.1)
Задача решается в уме за 1 минуту 1-им пятиклассником. 1 умножение, 1 сложение, 1 деление, 1 сравнение.
Разжевать? Нате
if (m>0 && h1<y*m/(x+m)<h2) visible = YES;
if (m>0 && h1<y*m/(x+m)<h2) visible = YES;
m — координата мальчика
(x,y) — координата входящего
(h1, h2) — границы зеркала.
(x,y) — координата входящего
(h1, h2) — границы зеркала.
Вы положили зеркало лежащим на плоскости x=0? Увы, но сделать произвольный поворот в пространстве — сама по себе непростая задача.
Не, повесил на стену. Это не очень сложно.
Покажите, как это сделать пятикласснику за минуту.
Рисуем вертикальный отрезок. Это зеркало.
Успел за 1 секунду.
Успел за 1 секунду.
Вы решили не ту задачу.
Простуженный Петя лежал в постели, как вдруг кто-то открыл дверь. Пете было лень вставать и он посмотрел в зеркало, чтобы увидеть кто пришёл. Известны координаты вошедшего (его можно считать материальной точкой), необходимо узнать, удасться ли Пете увидеть отражение вошедшего в зеркале. Зеркало имеет форму круга с центром в начале координат и расположено в плоскости ax + by + cz = 0. Петю тоже можно считать материальной точкой. Гарантируется, что Петя и незнакомец не лежат в плоскости зеркала и что Петя всегда видит отражающую сторону зеркала. Если изображение попадает на границу зеркала, то Петя видит вошедшего. Так как и Петю и вошедшего можно считать материальными точками, Петя может увидеть отражение вошедшего как сквозь вошедшего, так и сквозь свое собственное отражение.
Автор статьи также решает не ту задачу, а попроще. Я показал как решить в уме, ту, попроще.
Оригинальную задачу, пользуясь моим подходом, можно решить за 5 минут без бумаги, карандаша и справочника по аналитической геометрии.
В одну строчку.
Оригинальную задачу, пользуясь моим подходом, можно решить за 5 минут без бумаги, карандаша и справочника по аналитической геометрии.
В одну строчку.
Автор решает задачу попроще, чтобы показать, что она осталась сложной — следовательно, оригинальная еще сложнее.
Вы же упростили задачу и хвастаетесь самим фактом упрощения.
И извините, но пока вы не приведете решение оригинальной задачи, лично я вам на слово не поверю.
Вы же упростили задачу и хвастаетесь самим фактом упрощения.
И извините, но пока вы не приведете решение оригинальной задачи, лично я вам на слово не поверю.
Опуская инсинуации, привожу мысленное решение.
На первом этапе решаем задачу с зеркалом в плоскости x=0. a1b1c1 — враг a2b2c2 — мальчик.
отраженный враг -a1b1c1 точка пересечения отрезка отраженный враг — мальчик по методу подобных треугольников (пригодилось!) имеет координаты y=b2+a2*(b1-b2)/(a1+a2) и z=c2+a2*(c1-c2)/(a1+a2) Ответ да, если y^2+z^2<R^2
все просто — 1 минута. Теперь самое сложное — вернуть вектор 1 0 0 в abc. Не нарушая общности считаем abc нормальным. Вспоминаем плоскость — как вектор 1 0 повернуть в ab легко — все точки пересчитываем x0 = a*x + b*y y0=-b*x+a*y (еще полминуты на решение прошло) Третий этап самый сложный повернуть точку ab0 в точку abc.
На первом этапе решаем задачу с зеркалом в плоскости x=0. a1b1c1 — враг a2b2c2 — мальчик.
отраженный враг -a1b1c1 точка пересечения отрезка отраженный враг — мальчик по методу подобных треугольников (пригодилось!) имеет координаты y=b2+a2*(b1-b2)/(a1+a2) и z=c2+a2*(c1-c2)/(a1+a2) Ответ да, если y^2+z^2<R^2
все просто — 1 минута. Теперь самое сложное — вернуть вектор 1 0 0 в abc. Не нарушая общности считаем abc нормальным. Вспоминаем плоскость — как вектор 1 0 повернуть в ab легко — все точки пересчитываем x0 = a*x + b*y y0=-b*x+a*y (еще полминуты на решение прошло) Третий этап самый сложный повернуть точку ab0 в точку abc.
Пардон, отходил руки помыть. Так вот переход от (100) к (abc) это матрица поворота вокруг вектора (0, c, b) ) на угол фи, Нам нужен косинус его — косинус равен скалярному произведению вектор то есть равен а, а синус корень из 1-a*a или корень из b^2+с^2 — таким образом рождается гениальная формула перехода x0 = aa1*x + bb1*y+cc1*z, y0 = aa2*x + bb2*y+cc2*z. z0 = aa3*x + bb3*y+cc3*z. Я формулу помню, а школьникам придется решить систему уравнений. Итак коэффициент aa1 = a.
обозначим для простоты корень из b^2+с^2 за t. тогда коэффициент bb1 = t*b, cc1 = t*c. То есть x0 = a*x+ t*(b*y+c*z) Но x0 не нужен. нужны y0 и z0. Устал думать. Пойду чай выпью.
15:26 — 14:52 = 34 минуты. В 5 минут не уложились.
Я же не просто так к повороту придрался. Задача решается куда проще, если не пытаться ее упростить поворотами.
Я же не просто так к повороту придрался. Задача решается куда проще, если не пытаться ее упростить поворотами.
В любом случае, это задача скорее на математику и физику (геометрическая оптика), чем на программирование. Когда решение получено в рамках математики, то его очень просто запрограммировать. Программа превращается в простой расчет по аналитическим формулам. Такая задача больше подходит для олимпиад по математике и физике.
А если олимпиада по программированию — то основная сложность задачи должна проявляться в программировании, а не математике.
Я тоже, помню, участвовал в олимпиаде по программированию, 8й класс, и среди задач было: написать программу возведения матрицы в степень. А матрицы в школе вообще не изучаются, это тоже университетский материал! И что могли школьники себе думать? Большинство перемножили массивы с числами поэлементно. Лишь под конец тура зашел кто-то из организаторов и объяснил «настоящие» правила умножения матриц. Должно быть, кто-то смекнул, что от восьмиклассника неправомерно ожидать знания таких вещей. Правда, было слишком поздно. За оставшееся время решение не реализовал никто.
А если олимпиада по программированию — то основная сложность задачи должна проявляться в программировании, а не математике.
Я тоже, помню, участвовал в олимпиаде по программированию, 8й класс, и среди задач было: написать программу возведения матрицы в степень. А матрицы в школе вообще не изучаются, это тоже университетский материал! И что могли школьники себе думать? Большинство перемножили массивы с числами поэлементно. Лишь под конец тура зашел кто-то из организаторов и объяснил «настоящие» правила умножения матриц. Должно быть, кто-то смекнул, что от восьмиклассника неправомерно ожидать знания таких вещей. Правда, было слишком поздно. За оставшееся время решение не реализовал никто.
В ваших рассуждениях есть несколько ошибок. Первая — отсутствие тривиального решения в вашей голове не означает его отсутствия вообще. Вот несколько фактов из моей школьной геометрии, которых хватит, чтобы решить задачу.
1) Расстояние от точки до плоскости считается по формуле |Ax + By + Cz + D| / sqrt(A^2 + B^2 + C^2).
2) Вектор (A, B, C) является нормалью к плоскости Ax + By + Cz + D = 0.
Этого хватит, чтобы отразить точку P относительно плоскости. Дальше составляем параметрическое уравнение от одной переменной для прямой, проходящей через P' и Q. Решаем одно линейное уравнение, чтобы пересечь прямую с плоскостью. Ну и все, считаем расстояние, отвечаем на вопрос.
Вторая — всерос + Беларусь, даже без Питера и Москвы — это очень высокий уровень. У школьника с IOI таких вот задач за спиной сотни, у некоторых — тысячи. Линейную алгебру такие ребята знать должны. Это спорт, а не игра в смекалку. Объемы тренировок, знаний и навыков решают очень многое.
1) Расстояние от точки до плоскости считается по формуле |Ax + By + Cz + D| / sqrt(A^2 + B^2 + C^2).
2) Вектор (A, B, C) является нормалью к плоскости Ax + By + Cz + D = 0.
Этого хватит, чтобы отразить точку P относительно плоскости. Дальше составляем параметрическое уравнение от одной переменной для прямой, проходящей через P' и Q. Решаем одно линейное уравнение, чтобы пересечь прямую с плоскостью. Ну и все, считаем расстояние, отвечаем на вопрос.
Вторая — всерос + Беларусь, даже без Питера и Москвы — это очень высокий уровень. У школьника с IOI таких вот задач за спиной сотни, у некоторых — тысячи. Линейную алгебру такие ребята знать должны. Это спорт, а не игра в смекалку. Объемы тренировок, знаний и навыков решают очень многое.
Без знания или желания вывести точные формулы школьник может кстати двоичным поиском пользоваться — в плоскостях все линейно — и все сойдется быстро. Можно двигать плоскость пока она не начнет проходит через наблюдателя, а потом сделать гомотетию окружности на ее отражение (тоже двоичным поиском найдя пересечение луча и плоскости).
Пока не понимаю. Относительно чего вы делаете гомотетию?
Я в первой части ошибся, набирая комментарий. Надо искать плоскость которая проходит через вошедшего (а не наблюдателя), и это сделало бессмысленной вторую часть.
Я имел в ввиду, что можно делать гомотетию с центром гомотетии в отраженном наблюдателе, и применять ее к зеркалу, до момента пока плоскость последнего не станет содержать вошедшего. Все это, кажется, можно делать численно, если школьникам двоичный поиск ближе, чем аналитическое решение.
Я имел в ввиду, что можно делать гомотетию с центром гомотетии в отраженном наблюдателе, и применять ее к зеркалу, до момента пока плоскость последнего не станет содержать вошедшего. Все это, кажется, можно делать численно, если школьникам двоичный поиск ближе, чем аналитическое решение.
А давайте векторно.
Дано:
T = (xx, yy, zz) — Петя
S = (x0, y0, z0) — Входящий
P = (A, B, C) — Перпендикуляр к плоскости зеркала
X = (x, y, z) — Точка отражения входящего на плоскости
Во первых, сразу скажем, что не увидит, если точки T и S лежат по разные плоскости зеркала, т.е.
скалярые произведения PS и PT разных знаков, можно это записать как
if ((PS)*(PT) < 0) { не увидит }
Кстати, в решении так и написано: (P*S)*(P*T) = (A*x0+B*y0+C*z0)*(A*xx+B*yy+C*zz)
Пусть F = (T — X) + (S — X) = (T + S — 2X)
Пусть G = T + S, тогда F = G — 2X
По определению точки X, F коллинеарен P, запишем это:
P(G — 2X) = +-|P||G — 2X| или (PG-2PX)^2 = PP*(GG-4GX+4XX)
Известно, что PX=0, значит
PG*PG = PP*(GG-4GX+4XX)
А еще F перпендикулярен X, т.е.
2. X(G — 2X) = 0 или GX — 2XX = 0 или GX = 2XX
Подставляем GX:
PG*PG = PP*(GG-8XX+4XX) = PP*(GG-4XX) = PP*GG-4*PP*XX
XX = (PP*GG — PG*PG) / (4*PP)
Петя увидит входящего, если |X| <= R, т.е. XX <= R*R
Окончательно:
PP*GG-PG*PG <= 4*PP*R*R
Дано:
T = (xx, yy, zz) — Петя
S = (x0, y0, z0) — Входящий
P = (A, B, C) — Перпендикуляр к плоскости зеркала
X = (x, y, z) — Точка отражения входящего на плоскости
Во первых, сразу скажем, что не увидит, если точки T и S лежат по разные плоскости зеркала, т.е.
скалярые произведения PS и PT разных знаков, можно это записать как
if ((PS)*(PT) < 0) { не увидит }
Кстати, в решении так и написано: (P*S)*(P*T) = (A*x0+B*y0+C*z0)*(A*xx+B*yy+C*zz)
Пусть F = (T — X) + (S — X) = (T + S — 2X)
Пусть G = T + S, тогда F = G — 2X
По определению точки X, F коллинеарен P, запишем это:
P(G — 2X) = +-|P||G — 2X| или (PG-2PX)^2 = PP*(GG-4GX+4XX)
Известно, что PX=0, значит
PG*PG = PP*(GG-4GX+4XX)
А еще F перпендикулярен X, т.е.
2. X(G — 2X) = 0 или GX — 2XX = 0 или GX = 2XX
Подставляем GX:
PG*PG = PP*(GG-8XX+4XX) = PP*(GG-4XX) = PP*GG-4*PP*XX
XX = (PP*GG — PG*PG) / (4*PP)
Петя увидит входящего, если |X| <= R, т.е. XX <= R*R
Окончательно:
PP*GG-PG*PG <= 4*PP*R*R
Отражаем незнакомца относительно плоскости зеркала. Соединяем Петю и образ незнакомца прямой и смотрим точку ее пересечения с плоскостью зеркала. Проверяем, принадлежит ли эта точка зеркалу.
Автор делает ту же ошибку, что и типичный студент, освоивший началы матана и пытающийся доказать, что следующая задача нерешаема для школьников: «Взяли стакан молока и чашку чая. Набрали ложку молока из стакана, кинули в чай и размешали. Набрали ложку смеси из чашки, кинули в стакан и размешали. Чего больше: молока в чае или чая в молоке?», в то время, как многие школьники могут дать ответ моментально. Школьники, которые хоть немного решали геометрические задачи в олимпиадном программировании прекрасно умеют пересекать круг с прямой. Некоторые могут даже в восьмимерном пространстве пересечь.
прекрасно умеют пересекать круг с прямойконечно могут, я не возражаю, но кроме как решением СЛАУ координаты эти не найти
Или может более простые какие-то методы есть, просто их власти скрывают?
Все скептики почему-то не поняли морали этого топика — у вас есть (в среднем) 30 минут на то, чтобы: понять условие задачи, сформулировать правильно задачу, провести математические выкладки и вывести формулы для расчетов, написать программу, которая будет это считать. При этом забудьте про всякие объекты — векторы, матрицы и т.д., мы оперируем только простыми типами данных, наработками не пользуемся. Можем, конечно, написать свой тип данных, тот же вектор и переопределить для него элементарные операции сложения-умножения, но это лишняя трата времени из все тех же 30 минут.
Мат. выкладки — 2 минуты. Написание базовых операций — еще 2 минуты. Написание кода по выкладкам — минута. Осталось 25 минут на проверку.
Пусть у нас есть плоскость nr=b и прямая r=at+c. Подставим одно уравнение в другое и получим n(at+c) = b Отсюда t = (b — nc) / na и осталось подставить эту переменную в параметрическое уравнение прямой. Где тут СЛАУ? Правильный выбор представления исходных объектов все спрятал.
конечно могут, я не возражаю, но кроме как решением СЛАУ координаты эти не найти
Пусть у нас есть плоскость nr=b и прямая r=at+c. Подставим одно уравнение в другое и получим n(at+c) = b Отсюда t = (b — nc) / na и осталось подставить эту переменную в параметрическое уравнение прямой. Где тут СЛАУ? Правильный выбор представления исходных объектов все спрятал.
1. Матрицы школьник не знает и знать не обязан! Ну, может, в 2D знает повороты векторов — но без матриц, наподобие ( x cos a − y sin a; y cos a + x sin a ).
2. Снова-таки, мы теперь в дробной арифметике.
3. Есть только libc и STL, остальное нужно писать! Две минуты маловато даже для мегаспеца, который помнит код наизусть, не делает опечаток и не ошибается в копипасте. А в пункте 1 я вот не помню, где плюс и где минус; проверяю на простейших случаях — как повернёт (0,1) и (1,0), это тоже отнимает время. А каждая опечатка отнимает время, а ошибка на копипасте — вообще песец (замыленный глаз долго не видит, что где-то чего-то не изменил).
2. Снова-таки, мы теперь в дробной арифметике.
3. Есть только libc и STL, остальное нужно писать! Две минуты маловато даже для мегаспеца, который помнит код наизусть, не делает опечаток и не ошибается в копипасте. А в пункте 1 я вот не помню, где плюс и где минус; проверяю на простейших случаях — как повернёт (0,1) и (1,0), это тоже отнимает время. А каждая опечатка отнимает время, а ошибка на копипасте — вообще песец (замыленный глаз долго не видит, что где-то чего-то не изменил).
Мой скептицизм основан на личном опыте. Задачи на геометрию в большинстве своем довольно простые, т.к. ошибаться там особо негде и двумя тестами можно покрыть 90% возможных проблем. Сэкономленное на потенциальной отладке время достаточно велико, чтобы аккуратно посмотреть на задачу и понять, как она решается.
В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 9 классе проходят. Их отношение найти довольно легко по расстояниям до зеркала, затем надо в проекции на плоскость зеркала отрезок между двумя исходными точками поделить в той же пропорции и проверить на принадлежность кругу. Все операции описанные выше довольно тривиальны и любой школьник их легко выведет прямо на туре, если вдруг по какой-то причине он их не помнит.
В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 9 классе проходят. Их отношение найти довольно легко по расстояниям до зеркала, затем надо в проекции на плоскость зеркала отрезок между двумя исходными точками поделить в той же пропорции и проверить на принадлежность кругу. Все операции описанные выше довольно тривиальны и любой школьник их легко выведет прямо на туре, если вдруг по какой-то причине он их не помнит.
Если все так легко и просто на самом деле, то почему имеем то что имеем, а именно 0 (ни одного) решивших эту задачу участника?
Глядя на тся/ться ошибки в текстах условий могу предположить наличие на туре более простой задачи с косяком составителей, на поиск которого ушло много времени (ну или просто хорошо спрятанной подставой). Никак иначе я не могу объяснить существование серебрянного призера межнара, не решившего эту задачу.
конечно могут, я не возражаю, но кроме как решением СЛАУ координаты эти не найти
Или может более простые какие-то методы есть, просто их власти скрывают?
Насколько я помню, скалярное произведение в школе проходят.
Поэтому можно сделать так:
Пусть (x1,y1,z1) и (x2,y2,z2) — наши точки.
Считаем их проекцию на нормаль к плоскости (a,b,c):
u1=a*x1+b*y1+c*z1
u2=a*x2+b*y2+c*z2
Если u1*u2>0, то отрезок не пересекает плоскость. Иначе точкой пересечения (ей соответствует u=0) будет точка с параметром
t=u1/(u1-u2)
и точку пересечения можно найти как
x=x1+t*(x2-x1),
y=y1+t*(y2-y1),
z=z1+t*(z2-z1).
Никаких систем не обнаружено.
Или действительно можно подставить параметрическую запись координат точки на прямой в уравнение плоскости. Формулы будут те же.
del
Задача элементарная.
Находим координаты отражения незнакомца. Для этого вычтем из координат незнакомца удвоенную нормаль к плоскости помноженное на скалярное произведение нормали на координаты незнакомца.
Находим пересечение между плоскостью и линией от Пети до отражения. Просто решить две СЛАУ.
Если это пересечение лежит в сфере радиуса r — то ответ «Да», иначе — «Нет».
Находим координаты отражения незнакомца. Для этого вычтем из координат незнакомца удвоенную нормаль к плоскости помноженное на скалярное произведение нормали на координаты незнакомца.
Находим пересечение между плоскостью и линией от Пети до отражения. Просто решить две СЛАУ.
Если это пересечение лежит в сфере радиуса r — то ответ «Да», иначе — «Нет».
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор задачи «Зеркало в коридоре» и негодование