Я не понимаю, откуда такое мнение. 70% задач на геометрию — тупые построения, как обе задачи из этой темы. Из оставшихся задач 95% решаются сканлайном либо выпуклой оболочкой. Оставшиеся задачи используют геометрические примитивы только для формулировки: они либо основаны на вытаскивании чисел и запихивании их в структуру данных, либо очень технические и не требуют думать, а просто аккуратно реализовать 9000 шагов, описанных в условии. Последние тяжело назвать геометрическими, это все равно что считать задачи с домами задачами на архитектуру. Это все дополняется тем, что ответ часто дробный и можно одним тестом проверить весь код сразу с очень неплохим шансом. Если задачи на геометрию решаются плохо — обычно это значит, что кто-то перегробил геометрию в туре.
Глядя на тся/ться ошибки в текстах условий могу предположить наличие на туре более простой задачи с косяком составителей, на поиск которого ушло много времени (ну или просто хорошо спрятанной подставой). Никак иначе я не могу объяснить существование серебрянного призера межнара, не решившего эту задачу.
Мой скептицизм основан на личном опыте. Задачи на геометрию в большинстве своем довольно простые, т.к. ошибаться там особо негде и двумя тестами можно покрыть 90% возможных проблем. Сэкономленное на потенциальной отладке время достаточно велико, чтобы аккуратно посмотреть на задачу и понять, как она решается.
В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 9 классе проходят. Их отношение найти довольно легко по расстояниям до зеркала, затем надо в проекции на плоскость зеркала отрезок между двумя исходными точками поделить в той же пропорции и проверить на принадлежность кругу. Все операции описанные выше довольно тривиальны и любой школьник их легко выведет прямо на туре, если вдруг по какой-то причине он их не помнит.
Автор делает ту же ошибку, что и типичный студент, освоивший началы матана и пытающийся доказать, что следующая задача нерешаема для школьников: «Взяли стакан молока и чашку чая. Набрали ложку молока из стакана, кинули в чай и размешали. Набрали ложку смеси из чашки, кинули в стакан и размешали. Чего больше: молока в чае или чая в молоке?», в то время, как многие школьники могут дать ответ моментально. Школьники, которые хоть немного решали геометрические задачи в олимпиадном программировании прекрасно умеют пересекать круг с прямой. Некоторые могут даже в восьмимерном пространстве пересечь.
Зачем ехать на межнар не умея писать довольно простой перебор с комбинаторикой — мне не очень понятно, но это не важно. Попасть на финал из неизвестного вуза довольно легко и я слышал об энтузиастах, которые поступают в неизвестный вуз, чтобы проделать этот трюк.
МАИ, например, довольно часто светится, выставляет стабильно много команд и некоторые добиваются довольно серьезных успехов, но что-то я никогда не слышал, чтобы МАИ организовывала открытые олимпиады для школьников. Но это тоже неважно.
Называть олимпиаду международной можно только формально и инициатива выглядит, как попытка косить под почти идентично зовущийся IOI, в которой уровень слова «международный» совершенно иной. Но это тоже неважно.
Что важно — так это отношение организаторов. Глупые орфографические ошибки в условиях; картинки, которые даже на хабре всех путают, закрытые задачи и результаты; список победителей лежит на бывшей странице регистрации и у нее все еще неверный заголовок, призеров называют победителями, победителей — призерами и не дают им диплом первой степени, как это обычно принято; олимпиада не ориентирована на уровень ниже, чем у московских спецшкол, но серебряный призер IOI все равно участвует и еще миллион мелочей, явно показывающий, что на образовательные и рекламные цели олимпиады всем пофиг, а людей с прямыми руками, которые могут сделать все по-нормальному в вузе нет совсем.
Приглашаем на олимпиаду школьников из Беларуси, называем ее международной. Признак международной олимпиады — наличие школьников из по крайней мере двух стран, проверять тексты задач на ошибки уровня тся/ться для этого вовсе не обязательно. Мне вот интересно, откуда у неизвестных в олимпиадном программировании вузов такое стойкое желание организовать олимпиаду с как можно более громким названием?
Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.
Это неверно. Мы не можем уйти в стек больше, чем на O(n). Кроме того, можно аккуратно раскрыть хвостовую рекурсию и гарантировать O(log n) для глубины стека в худшем случае.
В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 9 классе проходят. Их отношение найти довольно легко по расстояниям до зеркала, затем надо в проекции на плоскость зеркала отрезок между двумя исходными точками поделить в той же пропорции и проверить на принадлежность кругу. Все операции описанные выше довольно тривиальны и любой школьник их легко выведет прямо на туре, если вдруг по какой-то причине он их не помнит.
МАИ, например, довольно часто светится, выставляет стабильно много команд и некоторые добиваются довольно серьезных успехов, но что-то я никогда не слышал, чтобы МАИ организовывала открытые олимпиады для школьников. Но это тоже неважно.
Называть олимпиаду международной можно только формально и инициатива выглядит, как попытка косить под почти идентично зовущийся IOI, в которой уровень слова «международный» совершенно иной. Но это тоже неважно.
Что важно — так это отношение организаторов. Глупые орфографические ошибки в условиях; картинки, которые даже на хабре всех путают, закрытые задачи и результаты; список победителей лежит на бывшей странице регистрации и у нее все еще неверный заголовок, призеров называют победителями, победителей — призерами и не дают им диплом первой степени, как это обычно принято; олимпиада не ориентирована на уровень ниже, чем у московских спецшкол, но серебряный призер IOI все равно участвует и еще миллион мелочей, явно показывающий, что на образовательные и рекламные цели олимпиады всем пофиг, а людей с прямыми руками, которые могут сделать все по-нормальному в вузе нет совсем.
Все это очень напоминает воронежскую олимпиаду: esci.ru/ttb/vserossiyskaya_studencheskaya_olympiada_in_informatics.htm. Когда я был школьником, я прочитал этот текст и точно знал, в какой вуз я никогда не пойду даже заглянуть внутрь.
Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).
O(n) не равно nlogn
Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.