
ZOJ Problem Set  3238
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 lowerleft point is (x1,y1)and the upperright 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 Source: ZOJ Monthly, August 2009 