Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Lucky Light
Description We have a (point) light source at position ( y) with _{L}y > 0, and a finite series of line segments, all of finite non-zero length, given by the coordinates of their two endpoints. These endpoints are all different. The line segments are all situated above the _{L}x-axis (y > 0).The segments cast their shadows onto the y-coordinates of the endpoints of the line segments. This guarantees that indeed each line segment has a bounded shadow on the x-axis.The collection of shadows divides the In the picture below the three line segments Input The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format: - One line with one integer
*n*with 0 ≤*n*≤ 100: the number of line segments. - One line with two integers
*x*and_{L}*y*, the coordinates of the light source, separated by a single space. The coordinates satisfy −100 ≤_{L}*x*≤ 100 and 1 ≤_{L}*y*≤ 1,000._{L} *n*lines, each containing four integers*x*,_{i}*y*_{i},*u*_{i}and*v*_{i}, separated by single spaces, that specify*x*- and*y*-coordinates of the two endpoints (*x*,_{i}*y*_{i}) and (*u*,_{i}*v*) of the_{i}*i*^{th}line segment, where −100 ≤*x*,_{i}*u*≤ 100 and 0 <_{i}*y*,_{i}*v*_{i}_{}<*y*, for 1 ≤_{L}*i*≤*n*.
Output For every test case in the input file, the output should contain a single number, on a single line: the number of lighted areas. Sample Input 2 3 50 60 55 45 30 35 64 39 92 18 20 30 40 16 2 -10 50 -10 1 10 11 -10 11 10 1 Sample Output 3 2 Hint The first test case below corresponds to the picture in the problem description. The second test case has two crossing line segments. Source |

[Submit] [Go Back] [Status] [Discuss]

Any problem, Please Contact Administrator