시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 128 MB 83 16 14 28.571%

문제

Given a circle, and a list of lines, how many parts has the circle been cut into? In the following example, four lines cut the circle into five parts.

입력

There will be several test cases in the input. Each test case will begin with four integers, r (1≤r≤1,000), x, y (-1,000≤x,y≤1,000), and n (0≤n≤1,000), where r is the radius of a circle, x and y are the coordinates of the center of the circle, and n is the number of lines. On each of the next n lines will be four integers, x1, y1, x2 and y2 (-1,000≤x1,y1,x2,y2≤1,000). These describe a line passing through (x1,y1) and (x2,y2). Note that we’re interested in the whole, infinite line, not just the segment between (x1,y1) and (x2,y2). In any test case, no more than two lines will intersect at any point inside the circle, no lines will be tangent to the circle, and no two lines will be coincident. The input will end with a line with four 0s.

출력

For each test case, output a single integer, indicating the number of parts that the circle is cut into. Output no spaces, and do not separate answers with blank lines.

예제 입력

16 1 7 4
-15 -9 14 -11
-4 30 -3 -20
-20 12 -10 7
17 10 31 0
0 0 0 0

예제 출력

5

힌트