Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3238
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.


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).


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


Author: WANG, Yelei
Source: ZOJ Monthly, August 2009
Submit    Status