Harry Potter and J.K.Rowling

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 685 Accepted Submission(s): 210

Problem Description In July 31st, last month, the author of the famous novel series J.K.Rowling celebrated her 46th birthday. Many friends gave their best wishes. They gathered together and shared one large beautiful cake.
Rowling had lots of friends, and she had a knife to cut the cake into many pieces. On the cake there was a cherry. After several cuts, the piece with the cherry was left for Rowling. Before she enjoyed it, she wondered how large this piece was, i.e., she wondered how much percentage of the cake the piece with the only cherry has.

Input First line has an integer T, indicating the number of test cases.
T test cases follow. The first line of each test case has one number r (1 <= r <= 10000) and one integer n (0 <= n <= 2000), indicating the radius of the cake and the number of knife cuts. n lines follow. The i-th line has four numbers, x1, y1, x2, y2. (x1, y1) and (x2, y2) are two points on the i-th cut. (-10000 <= x1, y1, x2, y2 <= 10000) The last line of each case has two number x, y, indicating the coordinate(x, y) of the cherry.

Technical Specification

1. R, x1, y2, x2, y2, x, y all have two digits below decimal points.
2. The center of the cake is always on the point (0, 0).
3. The cherry was always on the cake and would not be on the knife cuts.

Output For each test case, in one line output the case number and the percentage the piece with the cherry has of whole original cake, rounded to five fractional digits.
Sample Input

1
1.00 2
-1.00 0.00 1.00 0.00
0.00 -1.00 0.00 1.00
0.50 0.50

Sample Output

Case 1: 25.00000%

题目意思：有一块半径为r的圆形蛋糕，其中心在原点，有一个人在某一个点（x，y），现把蛋糕按两点所在直线切蛋糕，求切了n次后，这个人所在蛋糕的面积占总面积的百分比。
很容易想到计算每一条直线与圆的交点，半平面交求出多边形，然后求多边形与圆的面积交，
HDU坑爹，eps=1e-8就wa，1e-5就ac，蛋疼。
代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/4 15:03:55
File Name :20.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-5 #define pi acos(-1.0) typedef long long ll; int dcmp(double x){ if(fabs(x)
                
                 0 1:-1; } struct Point{ double x,y; Point(double _x=0,double _y=0){ x=_x;y=_y; } }; Point operator + (const Point &a,const Point &b){ return Point(a.x+b.x,a.y+b.y); } Point operator - (const Point &a,const Point &b){ return Point(a.x-b.x,a.y-b.y); } Point operator * (const Point &a,const double &p){ return Point(a.x*p,a.y*p); } Point operator / (const Point &a,const double &p){ return Point(a.x/p,a.y/p); } bool operator < (const Point &a,const Point &b){ return a.x
                 
                  =0; } Point GetLineIntersection(Point p,Point v,Point q,Point w){ Point u=p-q; double t=Cross(w,u)/Cross(v,w); return p+v*t; } Point GetLineIntersection(Line a,Line b){ return GetLineIntersection(a.p,a.v,b.p,b.v); } vector
                  
                    HPI(vector
                   
                     L){ int n=L.size(); sort(L.begin(),L.end());//将所有半平面按照极角排序。 int first,last; vector
                    
                      p(n); vector
                     
                       q(n); vector
                      
                        ans; q[first=last=0]=L[0]; for(int i=1;i
                       
                         p){ int n=p.size(); double ans=0; for(int i=1;i
                        
                         =0; } bool OnCircle(Point x,Circle c){ return dcmp(c.r-Length(c.c-x))==0; } int getSegCircleIntersection(Line L,Circle C,Point *sol){ Point nor=Normal(L.v); Line p1=Line(C.c,nor); Point ip=GetLineIntersection(p1,L); double dis=Length(ip-C.c); if(dcmp(dis-C.r)>0)return 0; Point dxy=vecunit(L.v)*sqrt(C.r*C.r-dis*dis); int ret=0; sol[ret]=ip+dxy; if(OnSegment(sol[ret],L.p,L.point(1)))ret++; sol[ret]=ip-dxy; if(OnSegment(sol[ret],L.p,L.point(1)))ret++; return ret; } double SegCircleArea(Circle C

HDU 3982 半平面交+圆与多边形面积交(一)

Harry Potter and J.K.Rowling