程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3982 半平面交+圓與多邊形面積交

HDU 3982 半平面交+圓與多邊形面積交

編輯：C++入門知識

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,Point a,Point b){  
    double a1=angle(a-C.c);  
    double a2=angle(b-C.c);  
    double da=fabs(a1-a2);  
    if(da>pi)da=pi*2-da;  
    return dcmp(Cross(b-C.c,a-C.c))*da*C.r*C.r/2.0;  
}  
double PolyCircleArea(Circle C,Point *p,int n){  
    double ret=0;  
    Point sol[2];  
    p[n]=p[0];  
    for(int i=0;i pp[2200];
Point p[100010];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int T,n;
     cin>>T;
     double R;
     Point dd;
     for(int t=1;t<=T;t++){
         scanf("%lf%d",&R,&n);
         Point a,b;
         vector L;
         Line s;
         a=Point(-20000,-20000);b=Point(20000,-20000);s=Line(a,b-a);L.push_back(s);
         a=Point(20000,-20000);b=Point(20000,20000);s=Line(a,b-a);L.push_back(s);
         a=Point(20000,20000);b=Point(-20000,20000);s=Line(a,b-a);L.push_back(s);
         a=Point(-20000,10000);b=Point(-20000,-20000);s=Line(a,b-a);L.push_back(s);
         for(int i=0;i ff=HPI(L);
         n=ff.size();
         for(int i=0;i