z-ray
Mr. Little Z is playing a new game. The game consists of Cartesian coordinate system in which there exist N line segments and one point (x,y). Mr. Little Z has to draw half-line from point (x,y).
The number of points is equal to the number of line segments intersected by the half-line. Little Z wants to know what is the minimal and maximal score he can achieve in this game.
InputIn the first line of the standard input there are 3 space separated integers, N ( 1 <= N <= 200000 ), x and y ( 0 <= |x|, |y| < 10000 ).
In the next N lines there are 4 space separated integers x1i, y1i, x2i, y2i( 0 < |x1i|, |y1i|, |x2i|, |y2i| <= 10000 ) that represent endpoints of i-th line segment.
Note:
- all points in standard input will be distinct
- points ( x1i, y1i ), ( x2i, y2i ) i ( x, y ) will not be co-linear.
- Little Z gets 1 point for line segment if he intersects it in any part of it including its both endpoints.
In the next N lines there are 4 space separated integers x1i, y1i, x2i, y2i( 0 < |x1i|, |y1i|, |x2i|, |y2i| <= 10000 ) that represent endpoints of i-th line segment.
Note:
- all points in standard input will be distinct
- points ( x1i, y1i ), ( x2i, y2i ) i ( x, y ) will not be co-linear.
- Little Z gets 1 point for line segment if he intersects it in any part of it including its both endpoints.
OutputTo the standard output write 2 space separated integers: the minimal and the maximal number of points Little Z can achieve.
Input:
Output:
4 1 2
3 -1 -2 8
4 0 -2 -2
-2 -3 -3 4
-4 3 2 4Output:
1 2Input:
Output:
2 -1 5
1 3 3 2
-4 2 2 -5Output:
0 1Input:
Output:
3 0 0
1 3 3 1
2 3 1 -1
-4 2 2 -5Output:
0 2Image: example
Third example: Line segments are colored blue. With red is colored one of possible half-lines that scores the minimal number of points and with green is colored one of possible half-lines that scores the maximal number of points.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.