Pull to refresh

Comments 53

Мораль сей публикации такова, что надо сначала подумать, а затем решать. Какого, извиняюсь, лешего, Вы зеркало описываете прямой ax+b?

Школьники поумнее заменят уравнение зеркала на x=0 и все Ваши зубодробительные формулы превратятся в тыкву. И никаких попиндикуляров искать не надо.

Впрочем, я могу ошибаться, но это вряд ли.
Возможно, но тут две вещи.
1. Не забывайте, перед нами школьники. Аналитическая геометрия — это, извините, 1-й курс вуза. В школе стоит обходиться только «интуитивными» векторными формулами в 2D, которые легко переизобрести, вроде косого произведения векторов. И уж точно ничего не множить на матрицы и не раскладывать по базисам.
2. Второй источник сложности в том, что надо остаться в целой арифметике!
P.S. Я и сам на украинской олимпиаде сталкивался с «забеганием вперёд». 8-й класс, хорошо решается через подобие (9 класс) и никак — если его не знаешь.

Я считаю, забегание вперёд — это плохо. Те, кого специально натаскивали, имеют преимущество перед теми, кто допёр сам.
Что тут плохого — это что, контрольная работа, обязательная для всего класса? Нет. Это олимпиада — занятие добровольное, для самых умных и увлечённых предметом, предполагать у них наличие знаний вне базового курса «для троешников» — это нормально. И да, «специально натасканные» имеют преимущество перед неподготовленными, так же как это происходит в спорте, бизнесе, да и вообще в жизни. А что, должно быть иначе?
В технических дисциплинах нет необходимости выходить за пределы базового курса. Можно придумать придумать много интересных задач которые решаются неочевидной комбинацией простых методов (или очевидной комбинацией сложных).

Суть олимпиады стимулировать креативность и способность выходить за рамки программы. Иначе вместо того чтобы отбирать людей способных написать учебник за N+1 год, мы будем отбирать только тех кто всего-лишь прочитал учебник за N+1 год. А что делать когда мы доберемся до Nmax, кто будет изобретать Nmax+1?
«Специально натасканные» — это те, у кого есть профессиональный тренер, разбирающийся в специфике дела! Но бывают и другие варианты…
• тренер кто попало, со спецификой олимпиад малознакомый;
• вместо тренера — задачник. Хорошо, сейчас интернет; у меня по информатике был один покровитель за 100 км, от него с оказией что-нибудь да и приходило флоппинетом.
UFO landed and left these words here
Согласен, возможно, я сам себе усложнил решение, когда ввел условие о целочисленном исчислении, но только это условие дает 100% верный результат; кто знает, но в вашем алгоритме если задать точку на границе зеркала она может не пройти…
и еще: во-первых, это усложнение заключается лишь в том, что нужно все хвосты (промежуточные вычисления) тащить за собой, а не просто сохранить в переменные.
во-вторых, ваше решение по объему выйдет не меньше чем мое, не так просто в математике уйти от сложности: попробуйте расписать свои пункты 1, 3 и 4 — вы получите те же несколько систем уравнений, но в довесок ко всему еще и несколько косинусов и арктангенсов (в п.1)
Задача решается в уме за 1 минуту 1-им пятиклассником. 1 умножение, 1 сложение, 1 деление, 1 сравнение.
Разжевать? Нате

if (m>0 && h1<y*m/(x+m)<h2) visible = YES;
m — координата мальчика
(x,y) — координата входящего

(h1, h2) — границы зеркала.
UFO landed and left these words here
UFO landed and left these words here
Автор статьи тоже решает в плоскости. Уверяю Вас, в трехмерном случае не сильно сложнее — главное, выбрать правильно систему координат)) (По-секрету, трехмерная также решается в уме, забудьте про эллипс, уж лучше гиперболический параболоид)
Вы положили зеркало лежащим на плоскости x=0? Увы, но сделать произвольный поворот в пространстве — сама по себе непростая задача.
Не, повесил на стену. Это не очень сложно.
Покажите, как это сделать пятикласснику за минуту.
Рисуем вертикальный отрезок. Это зеркало.

Успел за 1 секунду.
Вы решили не ту задачу.
Простуженный Петя лежал в постели, как вдруг кто-то открыл дверь. Пете было лень вставать и он посмотрел в зеркало, чтобы увидеть кто пришёл. Известны координаты вошедшего (его можно считать материальной точкой), необходимо узнать, удасться ли Пете увидеть отражение вошедшего в зеркале. Зеркало имеет форму круга с центром в начале координат и расположено в плоскости ax + by + cz = 0. Петю тоже можно считать материальной точкой. Гарантируется, что Петя и незнакомец не лежат в плоскости зеркала и что Петя всегда видит отражающую сторону зеркала. Если изображение попадает на границу зеркала, то Петя видит вошедшего. Так как и Петю и вошедшего можно считать материальными точками, Петя может увидеть отражение вошедшего как сквозь вошедшего, так и сквозь свое собственное отражение.
Автор статьи также решает не ту задачу, а попроще. Я показал как решить в уме, ту, попроще.

Оригинальную задачу, пользуясь моим подходом, можно решить за 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.
Пардон, отходил руки помыть. Так вот переход от (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 минут не уложились.

Я же не просто так к повороту придрался. Задача решается куда проще, если не пытаться ее упростить поворотами.
Я работаю, строчить мысли было некогда. Тем более излагать, решение минутное если честно. А матрицу поворота я наизусть знаю, поскольку у меня есть игра dice 5, в ней кубики крутятся вокруг произвольных прямых на угол дельта фи каждый кадр времени)
Рад за вас. Но знает ли эту матрицу гипотетический пятиклассник?..
Спасибо за вашу радость. Гипотетический пятиклассник решит двухмерную задачу, освежите память.
В любом случае, это задача скорее на математику и физику (геометрическая оптика), чем на программирование. Когда решение получено в рамках математики, то его очень просто запрограммировать. Программа превращается в простой расчет по аналитическим формулам. Такая задача больше подходит для олимпиад по математике и физике.

А если олимпиада по программированию — то основная сложность задачи должна проявляться в программировании, а не математике.

Я тоже, помню, участвовал в олимпиаде по программированию, 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 таких вот задач за спиной сотни, у некоторых — тысячи. Линейную алгебру такие ребята знать должны. Это спорт, а не игра в смекалку. Объемы тренировок, знаний и навыков решают очень многое.
Без знания или желания вывести точные формулы школьник может кстати двоичным поиском пользоваться — в плоскостях все линейно — и все сойдется быстро. Можно двигать плоскость пока она не начнет проходит через наблюдателя, а потом сделать гомотетию окружности на ее отражение (тоже двоичным поиском найдя пересечение луча и плоскости).
Пока не понимаю. Относительно чего вы делаете гомотетию?
Я в первой части ошибся, набирая комментарий. Надо искать плоскость которая проходит через вошедшего (а не наблюдателя), и это сделало бессмысленной вторую часть.
Я имел в ввиду, что можно делать гомотетию с центром гомотетии в отраженном наблюдателе, и применять ее к зеркалу, до момента пока плоскость последнего не станет содержать вошедшего. Все это, кажется, можно делать численно, если школьникам двоичный поиск ближе, чем аналитическое решение.
А давайте векторно.

Дано:
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 и S лежат в плоскости xy, а зеркало перпендикулярно этой плоскости

Невооруженным глазом видно, что утверждения о перпендикулярности P и X, F и X не верны, дальше рассуждать смысла нет
Вы не там X построили. X — это точка на плоскости зеркала, та самая, в которую надо смотреть Пете, чтобы увидеть входящего.

Хотя F от этого, конечно же, коллинеарным P не становится.

Увы P и F направлением не совпали все равно
Отражаем незнакомца относительно плоскости зеркала. Соединяем Петю и образ незнакомца прямой и смотрим точку ее пересечения с плоскостью зеркала. Проверяем, принадлежит ли эта точка зеркалу.
Вы мой алгоритм решения из статьи перефразировали что ли?
Автор делает ту же ошибку, что и типичный студент, освоивший началы матана и пытающийся доказать, что следующая задача нерешаема для школьников: «Взяли стакан молока и чашку чая. Набрали ложку молока из стакана, кинули в чай и размешали. Набрали ложку смеси из чашки, кинули в стакан и размешали. Чего больше: молока в чае или чая в молоке?», в то время, как многие школьники могут дать ответ моментально. Школьники, которые хоть немного решали геометрические задачи в олимпиадном программировании прекрасно умеют пересекать круг с прямой. Некоторые могут даже в восьмимерном пространстве пересечь.
прекрасно умеют пересекать круг с прямой
конечно могут, я не возражаю, но кроме как решением СЛАУ координаты эти не найти
Или может более простые какие-то методы есть, просто их власти скрывают?

Все скептики почему-то не поняли морали этого топика — у вас есть (в среднем) 30 минут на то, чтобы: понять условие задачи, сформулировать правильно задачу, провести математические выкладки и вывести формулы для расчетов, написать программу, которая будет это считать. При этом забудьте про всякие объекты — векторы, матрицы и т.д., мы оперируем только простыми типами данных, наработками не пользуемся. Можем, конечно, написать свой тип данных, тот же вектор и переопределить для него элементарные операции сложения-умножения, но это лишняя трата времени из все тех же 30 минут.
Мат. выкладки — 2 минуты. Написание базовых операций — еще 2 минуты. Написание кода по выкладкам — минута. Осталось 25 минут на проверку.

конечно могут, я не возражаю, но кроме как решением СЛАУ координаты эти не найти

Пусть у нас есть плоскость nr=b и прямая r=at+c. Подставим одно уравнение в другое и получим n(at+c) = b Отсюда t = (bnc) / na и осталось подставить эту переменную в параметрическое уравнение прямой. Где тут СЛАУ? Правильный выбор представления исходных объектов все спрятал.
1. Матрицы школьник не знает и знать не обязан! Ну, может, в 2D знает повороты векторов — но без матриц, наподобие ( x cos a − y sin a; y cos a + x sin a ).
2. Снова-таки, мы теперь в дробной арифметике.
3. Есть только libc и STL, остальное нужно писать! Две минуты маловато даже для мегаспеца, который помнит код наизусть, не делает опечаток и не ошибается в копипасте. А в пункте 1 я вот не помню, где плюс и где минус; проверяю на простейших случаях — как повернёт (0,1) и (1,0), это тоже отнимает время. А каждая опечатка отнимает время, а ошибка на копипасте — вообще песец (замыленный глаз долго не видит, что где-то чего-то не изменил).
Где вы у меня нашли хоть одну матрицу? Я считал исключительно в векторах.
И, кстати, где я эти вектора поворачивал?
Мой скептицизм основан на личном опыте. Задачи на геометрию в большинстве своем довольно простые, т.к. ошибаться там особо негде и двумя тестами можно покрыть 90% возможных проблем. Сэкономленное на потенциальной отладке время достаточно велико, чтобы аккуратно посмотреть на задачу и понять, как она решается.

В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 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).

Никаких систем не обнаружено.

Или действительно можно подставить параметрическую запись координат точки на прямой в уравнение плоскости. Формулы будут те же.
Задача элементарная.
Находим координаты отражения незнакомца. Для этого вычтем из координат незнакомца удвоенную нормаль к плоскости помноженное на скалярное произведение нормали на координаты незнакомца.
Находим пересечение между плоскостью и линией от Пети до отражения. Просто решить две СЛАУ.
Если это пересечение лежит в сфере радиуса r — то ответ «Да», иначе — «Нет».
Да, ошибся. Не СЛАУ. Просто подстановка. Но не суть. У меня на набросок решения ушло 5 минут.
Only those users with full accounts are able to leave comments. Log in, please.