Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
82 - ZOJ Monthly, August 2009 - H
Water Ring

Time Limit: 1 Second      Memory Limit: 32768 KB

After we place a wet cup on the table for a while, we pick it up and could see a water ring made by its buttom. When there are many pieces of paper on the table, some part of the ring will left on the papers instead of table. So, I am curious about the length of water ring left on the paper(the total lengh of the red arc). To make things easier, we assume that each paper is a rectangle and the sides are parallel to axes.

Input

There ara multiply cases (less than 50). Process to the end of file.

The first line of each test case contains two integers R and N (1 <= R <= 1000, 0 <= N <= 50), indicating the radius of the water ring and the number of papers on the table, the center of water ring is always (0,0). Each of the next N lines contains 4 integers x1,y1,x2,y2 (-1000 <= x1 <= x2 <= 1000,-1000 <= y1 <= y2 <= 1000) meaning that the paper is a rectangle that the lower-left point is (x1,y1)and the upper-right point is (x2,y2).

Output

For each test case ,output the length of water ring left on the paper. (accurate to 0.001)

Sample Input

5 1
0 0 4 3
5 1
-5 -5 5 5
10 2
-14 -13 12 -5
5 -9 8 12

Sample Output

0.000
31.416
24.981

Author: WANG, Yelei
Submit    Status