用三角剖分可以轻松搞定，数据也小 随便AC。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const double eps=1e-10,PI=acos(-1.0);
int cmp(double k)
{
return k<-eps ? -1:k>eps ? 1:0;
}
const double pi=acos(-1.0);
inline double sqr(double x)
{
return x*x;
}
struct point
{
double x,y;
point (){}
point (double a,double b):x(a),y(b){}
bool input()
{
return scanf("%lf%lf",&x,&y)!=EOF;
}
friend point operator +(const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator ==(const point &a,const point &b)
{
return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
friend point operator *(const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator*(const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator /(const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqr(x)+sqr(y);
}
};
double mysqrt(double x)
{
return sqrt(x);
}
double dot(const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
}
double cross(const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
}
double abs(const point &o)
{
return sqrt(dot(o,o));
}
void circle_cross_line(point a,point b,point o,double r,point ret[],int &num)
{
double x0=o.x,y0=o.y;
double x1=a.x,y1=a.y;
double x2=b.x,y2=b.y;
double dx=x2-x1,dy=y2-y1;
double A=dx*dx+dy*dy;
double B=2*dx*(x1-x0)+2*dy*(y1-y0);
double C=sqr(x1-x0)+sqr(y1-y0)-sqr(r);
double delta=B*B-4*A*C;
num=0;
if(cmp(delta)>=0)
{
double t1=(-B-mysqrt(delta))/(2*A);
double t2=(-B+mysqrt(delta))/(2*A);
if(cmp(t1-1)<=0&&cmp(t1)>=0)
{
ret[num++]=point(x1+t1*dx,y1+t1*dy);
}
if(cmp(t2-1)<=0&&cmp(t2)>=0)
{
ret[num++]=point(x1+t2*dx,y1+t2*dy);
}
}
}
point crosspt(const point &a,const point &b,const point &p,const point &q)
{
double a1=cross(b-a,p-a);
double a2=cross(b-a,q-a);
return (p*a2-q*a1)/(a2-a1);
}
double sector_area(const point &a,const point &b,const double r)
{
double theta=atan2(a.y,a.x)-atan2(b.y,b.x);
while(cmp(theta)<=0)theta+=2*PI;
while(cmp(theta-2*PI)>0)theta-=2*PI;
theta=min(theta,2*PI-theta);
return r*r*theta/2.;
}
double calc_c(const point &a,const point &b,const double r)
{
point p[2];
int num=0;
bool ina=cmp(abs(a)-r)<0;
bool inb=cmp(abs(b)-r)<0;
if(ina)
{
if(inb)return fabs(cross(a,b))/2.;
else
{
circle_cross_line(a,b,point(0,0),r,p,num);
return fabs(sector_area(b,p[0],r))+fabs(cross(a,p[0]))/2.;
}
}
else
{
if(inb)
{
circle_cross_line(a,b,point(0,0),r,p,num);
return fabs(sector_area(p[0],a,r))+fabs(cross(p[0],b))/2.;
}
else
{
circle_cross_line(a,b,point(0,0),r,p,num);
if(num==2)
{
return fabs(sector_area(a,p[0],r))+fabs(sector_area(p[1],b,r))+fabs(cross(p[0],p[1]))/2.;
}else
{
return fabs(sector_area(a,b,r));
}
}
}
}
double area(int n,point res[],double r)
{
double ret=0.;
for(int i=0;i<n;i++)
{
int sgn=cmp(cross(res[i],res[(i+1)%n]));
if(sgn!=0)
{
ret+=sgn*calc_c(res[i],res[(i+1)%n],r);
}
}
return ret;
}
point pp[100];
int main()
{freopen("t.txt","r",stdin);
double r;
int n;
while(scanf("%lf",&r)!=EOF)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
pp[i].input();
pp[n]=pp[0];
printf("%.2f
",fabs(area(n,pp,r))+eps);
}
return 0;
}