Примат должен открыть свой разум фантазии оставаясь в рамках логики
Задача Две землеройки постоянно находятся на спине питона в точках [latex]A[/latex] и [latex]C[/latex]. Однако, по неизвестной причине в момент времени [latex]t_A[/latex] первая землеройка отправляется в пункт [latex]B[/latex] с расчётным временем прибытия [latex]t_B[/latex]. Поскольку такое поведения является характерным для землероек вообще, вторая поступила также и в момент времени [latex]t_C[/latex] отправилась в пункт [latex]D[/latex] с расчётным временем прибытия [latex]t_D[/latex]. На новом месте землеройки в дальнейшем планирует находиться постоянно. Известно, что землеройки обычно движутся по питонам с постоянной скоростью стараясь держаться центра спины, чтобы не соскальзывать. Питоны же во время движения землероек спокойно лежат без самопересечений. Дано: Точки [latex]A, B, C, D[/latex] задаются расстоянием от кончика хвоста питона, измеренным вдоль обычного маршрута землероек. Время старта и прибытия землероек также задано. Входные данные задаются целыми числами не превосходящими по модулю 10000 в следующем формате:Эта задача буквально должна вывести Вас в следующее измерение.
Если Вы конечно согласитесь.
| [latex]A[/latex] | [latex]t_A[/latex] |
| [latex]B[/latex] | [latex]t_B[/latex] |
| [latex]C[/latex] | [latex]t_C[/latex] |
| [latex]D[/latex] | [latex]t_D[/latex] |
Подсказка
Жизнь землероек на графиках
Название задачи призвано наводить на мысль о системе декартовых координат, где по одной оси измеряется время начала и конца движения землероек, а по другой оси — координаты точки на спине питона, в которой они находятся. Из взаимного расположения отрезков, олицетворяющих путь нерадивых млекопитающих, можно определить, столкнутся ли они.
Следовательно, задача сводится к вопросу: пересекаются ли отрезки, заданные координатами двух точек? Наиболее очевидный способ выяснить это — определить, имеют ли отрезки общие интервалы значений ( в проекции на координатные оси ), а затем выписать общие уравнения прямых, заданных некими двумя точками, и подставить в него две оставшиеся пары координат. По свойству общего уравнения прямой, полученное значение будет больше нуля, если точка лежит в правой полуплоскости относительно направленности прямой, меньше нуля, если точка лежит в левой полуплоскости, и равно нулю, если точка лежит на отрезке. Следовательно, если произведение полученных результатов окажется меньше или равно нулю, отрезки пересекаются.
http://ideone.com/iRLNzT
Начало размышления абсолютно верное.
К сожалению, Вы не заметили, что эта задача несколько сложнее чем пересечение отрезков.
Кроме того Ваше решение для пересечения отрезков не проходит тесты на e-olimp.
Я даже засомневался в правильности их тестов, но моё решение принято.
Задачу про пересечение отрезков я в конце концов сдал: как оказалось, целочисленного типа int не хватало в некоторых граничных случаях.
В связи с этим я адаптировал решение к данной задаче, взяв за основу следующие рассуждения:
пока землеройка находится в движении, она может
а) столкнуться с ничего не подозревающей землеройкой, стоящей на месте ( до начала её движения или после его окончания);
б) столкнуться лоб-в-лоб с другой бегущей землеройкой;
Данным случаям графически можно сопоставить
а) пересечение отрезков прямых вида B*x = C (землеройка в состоянии покоя) и A1*y +B1*x=C1 (бегущая землеройка) или как пересечение вертикальной линии с наклонной ;
б) пересечение двух отрезков прямых вида A*y+B*x+C=0 (бегущие землеройки), или как пересечение наклонных линий с наклонными:
Возможность столкновения землероек проверяем из таких соображений:
а) наличие у их движения общих интервалов по оси абсцисс (точки на теле питона);
б) общее уравнение прямой при подстановке в него точек, не задающих данную прямую, принимает разные знаки, если точки лежат по разные стороны от прямой.
Соответственно, необходимо составить шесть уравнений прямых (по два для вертикальных участков на графике для каждой землеройки и по одному для иллюстрации их движения) и провести соответствующие вычисления.
Программный код доступен по ссылке:
http://ideone.com/FjdLoO
Вопрос организационный: варианты решения задач word-of-the-week оформлять в рубрике «Поисковые задачи»? К записи и тесты прикрепить можно, и картинки (для наглядности рассуждений).
Да, конечно