Задача
Две землеройки постоянно находятся на спине питона в точках [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[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex] задаются расстоянием от кончика хвоста питона, измеренным вдоль обычного маршрута землероек. Время старта и прибытия землероек также задано. Входные данные задаются целыми числами не превосходящими по модулю 10000 в следующем формате:
| A | t_A |
| B | t_B |
| C | t_C |
| D | t_D |
Найти:
Необходимо определить, удастся ли землеройкам проделать этот маневр или в результате столкновения они свалятся с питона. Если питону удастся избавиться от докучливых землероек выведите “Yes”, в противном питону случае – “No”.
Тесты
| A | B | C | D | Результат | Комментарий | |||
| i | 0 | 10000 | 0 | 10000 | Yes | Пересечение крест-накрест | ||
| t_i | 0 | 10000 | 10000 | 0 | ||||
| i | -1 | 1 | 2 | 3 | No | Нет общего интервала значений по оси абсцисс | ||
| t_i | -1 | 1 | 2 | 3 | ||||
| i | 0 | 1 | 1 | 0 | Yes | Столкновение движущейся и покоящейся землероек | ||
| t_i | 0 | 1 | 1 | 3 | ||||
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <algorithm> using namespace std; //check common interval existence inline bool range(long n1, long n2, long n3, long n4) { return min(n3, n4) <= max(n1, n2) && max(n3, n4) >= min(n1, n2); } bool intersect( long A, long tA, long B, long tB, long C, long tC, long D, long tD ) { long a1 = tA-tB; long a2 = tC-tD; long b1 = B-A; long b2 = D-C; long c1 = A*tB - B*tA; long c2 = c1 = C*tD - D*tC; long r1 = a1*C+b1*tC+c1; long r3 = a2*A+b2*tA+c2; long r2 = a1*D+b1*tD+c1; long r4 = a2*B+b2*tB+c2; if (r1*r2 <= 0 && r3*r4 <= 0) return true; return false; } int main() { long A, B, C, D; //X-axis long tA, tB, tC, tD; //Y-axis cin>> A >> tA; cin>> B >> tB; cin>> C >> tC; cin>> D >> tD; if (range(A, B, C, D)) { //if both dots lie in different semiareas, or at least one of them lies on the segment bool r1 = intersect(A, tA, B, tB, C, tC, D, tD); //{(A,tA), (B,tB)} and {(C, tC), (D, tD)} bool r2 = intersect(A, tA, B, tB, C, 0, C, tC); //{(A,tA), (B,tB)} and {(C, 0), (C, tC)} bool r3 = intersect(A, tA, B, tB, D, tD, D, tD+tB); //{(A,tA), (B,tB)} and {(D, tD), (D, tD+tB)} bool r4 = intersect(C, tC, D, tD, A, 0, A, tA); //{(C,tC), (D,tD)} and {(A, 0), (A, tA)} bool r5 = intersect(C, tC, D, tD, B, tB, B, tB+tD); //{(C,tC), (D,tD)} and {(B, tB), (B, tB+tD)} if (r1 || r2 || r3 || r4 || r5) //if at least one term is true { cout<<"Yes\n"; return 0; } } cout<<"No\n"; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.*; import java.lang.*; import java.io.*; import java.math.*; class Ideone { //check common interval existence public static boolean segmentsOverlap(long l1, long r1, long l2, long r2){ //segments [l1, r1], [l2, r2] (segment borders may not be sorted) //there is an intersection iff segments are neither located //this way [l1, r1] ... [l2, r2] nor this [l2, r2] ... [l1, r1] return !(Math.max(l2, r2) < Math.min(l1, r1) || Math.max(l1, r1) < Math.min(l2, r2)); } public static int sign(long n){ if(n < 0) return -1; if(n > 0) return 1; return 0; } public static boolean segmentsIntersect(long A, long tA, long B, long tB, long C, long tC, long D, long tD){ //find out the equations of the lines segments lie on //if segments intersect, both endpoints of one are located at //different half-planes relatively to second line //a1*X + b1*tX + c1 == 0 //a2*X + b1*tX + c2 == 0 long a1 = tA-tB; long a2 = tC-tD; long b1 = B-A; long b2 = D-C; long c1 = A*tB-B*tA; long c2 = C*tD-D*tC; long r1 = a1*C+b1*tC+c1; long r3 = a2*A+b2*tA+c2; long r2 = a1*D+b1*tD+c1; long r4 = a2*B+b2*tB+c2; return sign(r1)*sign(r2) <= 0 && sign(r3)*sign(r4) <= 0; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); long A = in.nextLong(); long tA = in.nextLong(); long B = in.nextLong(); long tB = in.nextLong(); long C = in.nextLong(); long tC = in.nextLong(); long D = in.nextLong(); long tD = in.nextLong(); if(segmentsOverlap(A, B, C, D) == true){ //bots dots either lie in different half-planes or //at least one of them lies on the segment boolean r1 = segmentsIntersect(A, tA, B, tB, C, tC, D, tD); //[(A,tA), (B,tB)] and [(C, tC), (D, tD)] boolean r2 = segmentsIntersect(A, tA, B, tB, C, 0, C, tC); //[(A,tA), (B,tB)] and [(C, 0), (C, tC)] boolean r3 = segmentsIntersect(A, tA, B, tB, D, tD, D, tD+tB); //[(A,tA), (B,tB)] and [(D, tD), (D, tD+tB)] boolean r4 = segmentsIntersect(C, tC, D, tD, A, 0, A, tA); //[(C,tC), (D,tD)] and [(A, 0), (A, tA)] boolean r5 = segmentsIntersect(C, tC, D, tD, B, tB, B, tB+tD); //[(C,tC), (D,tD)] and [(B, tB), (B, tB+tD)] if(r1 || r2 || r3 || r4 || r5) System.out.println("Yes"); else System.out.println("No"); } } } |
Анализ. Формализация задачи.
Название задачи намекает на построение графика зависимости координаты от времени: 
Промежутки неподвижности землероек обозначены на данном графике вертикальными линиями, движения — наклонными.
При таком подходе задачу можно свести к конкретной математической проблеме: определить, пересекает ли отрезок, не параллельный оси ординат, ломаную.
Алгоритм решения.
- Определить, имеют ли ломаные общий интервал значений по оси абсцисс. Если его нет, то пересечься они не могут. Проверку по оси ординат проводить не нужно, т.к. вертикальные участки ломаных не ограничены сверху.
- Составить шесть общих уравнений прямых, проходящих через две заданные точки.
[latex]\frac {y-y1}{y2-y1} = \frac {x-x1}{x2-x1}[/latex].
То же самое, что и:
[latex] (y_{1} — y_{2})x + (x_{2} — x_{1})y + (x_{1}y_{2} — x_{2}y_{1}) = 0[/latex]. (*) - По свойству общего уравнения прямой, при подстановке точки в уравнение (*) возможны три случая: полученное значение меньше, больше или равно нулю. Соответственно, точка либо лежит в левой или правой полуплоскостях, либо она лежит на прямой. Если при подстановке концов отрезка получим значения разных знаков, то отрезок пересекает прямую.
- Пересечься землеройки могут в двух случаях:
- Когда первая движется, а вторая — нет.
- Когда они движутся одновременно.
На координатной плоскости эти случаи соответствуют пересечению наклонной и вертикальной линии или двух наклонных. Следовательно, необходимо проверить, пересекается ли промежуток движения одной землеройки с двумя интервалами покоя и интервалом движения второй землейроки, потом повторить процедуру с позиции другой землеройки.
Детали реализации:
Для определения, пересекаются ли отрезок и ломаная или нет, использована булева функция. Для поиска максимума двух чисел использована функция swap из заголовочного файла algorithm.
Корректность работы алгоритма, определяющего, пересекаются ли два отрезка, заданные координатами своих концов, подтверждают пройденные тесты на сайте e-olimp: http://www.e-olimp.com/solutions/1597737
Протестировать решение можно по ссылке: http://ideone.com/FjdLoO
Решение на Java: http://ideone.com/AxLzPh
Хорошо, но…
— Ссылки в самом конце лучше делать именно как ссылки.
— В таблицах всё куда-то уехало.
— Условные операторы почему-то излишне сдвигаются
— Нумерованные списки (ordered list) задаётся командой OL. Отдельные пункты списка — (list item) LI
Ваши замечания учтены и исправлены, за исключением разметки таблиц: на локальной машине она отображается корректно, при вставке на сайт же правый столбец уезжает по неочевидной для меня причине. На следующем занятии я покажу вам исходный код записи, может, я уже не вижу, в чем там фатальный недостаток.
Java версия засчитана, 10 баллов.