Офис одной из IT-компаний при виде сверху представляет собой квадрат со сторонами длины $$$n$$$. Для удобства введем систему координат и расположим на ней офис так, что левый-нижний угол офиса будет иметь координаты $$$(0,0)$$$, а правый-верхний — координаты $$$(n,n)$$$. При этом левая стена офиса лежит на оси $$$OY$$$, а нижняя — на оси $$$OX$$$ (см. рисунок ниже). Правой и верхней стен в офисе нет, вместо них по всей длине стороны квадрата расположены окна.
Приближается лето, поэтому солнце всё чаще заглядывает в офис. Лучи солнца движутся в направлении вектора $$$(x_s,y_s)$$$. Можно считать, что солнце достаточно большое и через каждую точку проходит ровно один такой луч.
В офисе расположены $$$k$$$ компьютерных столов, каждый из которых можно представить в виде отрезка. Лучи солнца проходят через окна и попадают на компьютерные столы. Конечно, это доставляет неудобства разработчикам и препятствует развитию IT-индустрии. Для устранения проблемы было решено применить инновационный метод — занавески. Занавески можно вешать на окна и тем самым частично блокировать проникновение лучей в офис. Более формально, любую часть окон можно завесить занавесками; если луч света попадает на занавеску, то он не проходит в офис. На картинке ниже красным цветом отмечена занавеска, которая блокирует попадание на стол лучей солнца, движущихся вдоль вектора $$$(-2, 0)$$$:
Разумеется, нужно повесить занавески таким образом, чтобы лучи солнца не попали ни на один компьютерный стол. С другой стороны, разработчики соскучились по ярким летним дням, поэтому суммарная длина занавесок должна быть минимально возможной. Помогите IT-индустрии — найдите эту длину!
В первой строке записаны три целых числа $$$n$$$, $$$x_s$$$ и $$$y_s$$$ ($$$2 \leq n \leq 10^9$$$, $$$-10^9 \leq x_s, y_s \leq 0$$$, $$$x_s + y_s \lt 0$$$) — размер офиса и направление лучей солнца.
Вторая строка содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 2\cdot 10^5$$$) — количество столов в офисе.
В каждой из следующих $$$k$$$ строк записаны 4 натуральных числа $$$x_{1i}$$$, $$$y_{1i}$$$, $$$x_{2i}$$$, $$$y_{2i}$$$ ($$$0 \lt x_{1i}, y_{1i}, x_{2i}, y_{2i} \lt n$$$), обозначающие координаты одного конца стола $$$(x_{1i}, y_{1i})$$$ и координаты другого конца стола — $$$(x_{2i}, y_{2i})$$$. Столы могут пересекаться или даже совпадать.
Выведите единственное вещественное число — минимальную суммарную длину занавесок.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
В тестах общей стоимостью не менее 30 баллов дополнительно выполняется $$$x_s=0$$$ или $$$y_s=0$$$.
В тестах общей стоимостью не менее 30 баллов дополнительно выполняется $$$k=1$$$.
6 -2 0 1 2 1 4 2
1.000000
6 0 -2 1 2 1 4 2
2.000000
6 -2 -1 1 2 1 4 2
0.000000
6 -2 -3 2 2 1 4 2 1 3 2 3
2.666667
6 -2 -3 2 2 1 4 2 1 3 4 3
4.000000
Картинка в условии соответствует первому примеру.
Во втором примере расположение стола такое же, как и в первом, но лучи солнца движутся вертикально:
В третьем примере стол расположен параллельно лучам солнца, поэтому требуется занавеска длины 0:
В четвертом примере для каждого стола требуется отдельная занавеска:
В пятом примере одна занавеска защищает оба стола от попадания солнечных лучей:
