Задача

Как это выглядит на координатной плоскости

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X_0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $Y=0$.

Входные данные: во входном файле в первой строке содержатся два целых числа через пробел – координата $X_0$ точки появления капли $(0 < X_0 < 10000)$ и количество отрезков-препятствий $N(0≤N≤100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x_1, y_1, x_2, y_2$ – координаты левого и правого концов отрезка-препятствия $($все числа целые и находятся в диапазоне от $0$ до $10000, x_1 < x_2, y_1 ≠y_2)$. Отрезки не пересекаются и не соприкасаются.

Выходные данные: в выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Код программы

Решение задачи

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

1. Если $X\in[x_1,x_2]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
2. Тогда мы сравниваем координаты $y_1$ и $y_2$, выбираем из них наименьшее и присваиваем соответствующую координату $x_1$ или $x_2$ координате
   нашей капли $X$.
3. Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com