Art Academy VI: The Last Stand

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

hewmatt10 has been cornered!

With his Art Academy in ashes, his artworks missing, his friends all having left him, and his entire life in shambles, he has constructed a massive army with all of his forces in a last stand. The structure of his army is composed of N line segments. Somewhere in the area, he has also hidden himself away in a secret bunker, at coordinates (x, y).

Knowing this information, A_L_I_C_E_ has ordered her subject, yeahbennou, to destroy the bunker and end the terror, once and for all. Since calculating curved trajectory is hard, he will send his missiles only in straight lines, starting from the x-axis, firing directly towards the bunker. However, being a merciful person, he will try to avoid hitting hewmatt10's army at all costs, as they are not all as evil as him.

Weighing his options, yeahbennou would like to ask you a question:

What is the total length of the range that yeahbennou can fire from in order to hit hewmatt10's bunker without hitting his army, if he can only fire starting from the x-axis, in the range [l, r], where the bunker is at (x, y)?

It is guaranteed that the y-position of his bunker will be strictly greater than the entirety of his army. In other words, his army will always be between the x-axis and his bunker.

Input Specification

On the first line, there is a single integer N, representing the number of lines in hewmatt10's army. (1 \le N \le 10^5).

The second line will contain four space-separated integers, l, r, x and y. (0 \le l \le r \le 10^9), (0 \le x \le 10^9), (1 < y \le 10^9).

The next N lines will contain four space-separated integers, x_1, y_1, x_2, y_2, meaning that there is a line segment from the point (x_1, y_1) to the point (x_2, y_2). (0 \le x_1, x_2 \le 10^9), (0 < y_1, y_2 < y), representing a part of the army. It is guaranteed that these two points will be distinct.

Output Specification

Output the total length of the range which yeahbennou can fire from in order to hit hewmatt10's bunker without hitting his army.

Your answer will be considered correct if the absolute difference from the official answer is at most 10^{-3}.


Subtask 1 [30%]

N = 1

Subtask 2 [70%]

No additional constraints.

Sample Input

1 10 3 3
1 2 3 1

Sample Output



The green region represents the area which can be fired from. However, since you can only fire from the x-axis, in the range [1, 10] as specified by the input, the only valid range is from [3, 10], which has a length of 7.


There are no comments at the moment.