NC13817. Find Quailty
描述
输入描述
第一行是一个正整数T(≤ 1000)，表示测试数据的组数， 对于每组测试数据， 第一行是一个整数n(3≤ n ≤ 100)，表示凸多边形体育馆的顶点数， 接下来n行，每行是两个整数x_i,y_i(-1000 ≤ x_i,y_i ≤ 1000)，按照逆时针的顺序给出体育馆的n个顶点， 最后一行是三个整数x_p,y_p,T(-1000 ≤ x_p,y_p ≤ 1000, 1 ≤ T ≤ 4000)，表示位置P的坐标（保证不在多边形内，但可能在多边形的顶点或者边上）和小Q同学的失踪时间， 保证满足n>10的数据不超过100组。
输出描述
对于每组测试数据，输出由小Q同学现在可能出现的位置构成的区域的面积，要求相对误差不超过1e-6。 也就是说，令输出结果为a，标准答案为b，若满足fabs((a - b)/max(1.0, b))≤1e-6，则输出结果会被认为是正确答案。
示例1
输入:
2 4 0 0 2 0 2 2 0 2 3 1 1 4 0 0 2 0 2 2 0 2 3 1 3
输出:
3.141592653590 24.180805801865
C++14(g++5.4) 解法, 执行用时: 219ms, 内存消耗: 672K, 提交时间: 2020-07-10 22:16:29
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
typedef long double db;
const db PI=acos(-1.0);
const db eps=1e-9;
inline int sgn(db x)
{
return (x>eps ? 1 : (x<-eps ? -1 : 0));
}
struct Point
{
db x,y;
Point() {}
Point(db _x,db _y):x(_x),y(_y) {}
Point operator + (const Point &t)const
{
return Point(x+t.x,y+t.y);
}
Point operator - (const Point &t)const
{
return Point(x-t.x,y-t.y);
}
Point operator * (const db &t)const
{
return Point(x*t,y*t);
}
Point operator / (const db &t)const
{
return Point(x/t,y/t);
}
db operator * (const Point &t)const
{
return x*t.y-y*t.x;
}
db operator ^ (const Point &t)const
{
return x*t.x+y*t.y;
}
db len()const
{
return sqrt(x*x+y*y);
}
db arc(const int &on=0)const
{
db t=atan2(y,x);
if(t<(on ? 1 : -1)*eps)t+=2*PI;
return t;
}
db arc(const Point &t)const
{
db r=((*this)^t)/((*this).len()*t.len());
return acos(max(-1.0L,min(1.0L,r)));
}
friend istream& operator >> (istream &in,Point &t)
{
in>>t.x>>t.y;
return in;
}
friend ostream& operator << (ostream &out,const Point &t)
{
out<<"("<<t.x<<","<<t.y<<")";
return out;
}
};
struct Segment
{
Point s,e;
Segment() {}
Segment(Point _s,Point _e):s(_s),e(_e) {}
db get_ratio(const Point &t)const
{
return ((t-s)^(e-s))/((e-s)^(e-s));
}
Point get_point(const db &t)const
{
return s+(e-s)*t;
}
db cal_contribution(const db &a,const db &b)
{
return get_point(a)*get_point(b)/2;
}
bool on_segment(const Point &t)const
{
if(sgn((t-s)*(t-e)))return 0;
db r=get_ratio(t);
return sgn(r)>=0 && sgn(r-1)<=0;
}
vector<Point> operator & (const Segment &t)const
{
vector<Point> res;
if(sgn((e-s)*(t.e-t.s))==0)
{
if(on_segment(t.s))res.push_back(t.s);
if(on_segment(t.e))res.push_back(t.e);
if(t.on_segment(s))res.push_back(s);
if(t.on_segment(e))res.push_back(e);
return res;
}
db r=((t.s-s)*(t.e-t.s))/((e-s)*(t.e-t.s));
Point p=get_point(r);
if(on_segment(p) && t.on_segment(p))
res.push_back(p);
return res;
}
};
struct Circle
{
Point o;
db r,a,b;
Circle() {}
Circle(Point _o,db _r,db _a=0,db _b=2*PI):o(_o),r(_r),a(_a),b(_b) {}
db get_arc(const Point &t)const
{
return (t-o).arc(a>eps);
}
bool in_circle(const Point &t,const int &cir=0,const int &lef=0,const int &rig=0)const
{
db d=(o-t).len();
if(sgn(d-r)>=cir)return 0;
if(sgn(d)==0)return 1;
db s=get_arc(t);
return sgn(s-a)>-lef && sgn(s-b)<rig;
}
bool on_circle(const Point &t)const
{
db d=(o-t).len();
if(sgn(d-r))return 0;
if(sgn(r)==0)return 1;
db s=get_arc(t);
return sgn(s-a)>=0 && sgn(s-b)<=0;
}
Point get_point(const db &t)const
{
return o+Point(cos(t),sin(t))*r;
}
db cal_contribution(const db &a,const db &b)const
{
return (get_point(a)*get_point(b)+r*r*((b-a)-sin(b-a)))/2;
}
db cal_area()const
{
return r*r*(b-a)/2;
}
vector<Point> operator & (const Segment &t)const
{
vector<Point> res;
Point m=t.s+(t.e-t.s)*t.get_ratio(o);
Point v=(t.e-t.s)/(t.e-t.s).len();
db d=(m-o).len();
if(sgn(d-r)>0)return res;
d=sqrt(max(0.0L,r*r-d*d));
for(int i=-1; i<=1; i+=2)
{
Point p=m+v*d*i;
if(on_circle(p) && t.on_segment(p))
res.push_back(p);
}
return res;
}
vector<Point> operator & (const Circle &t)const
{
vector<Point> res;
db d=(o-t.o).len();
if(sgn(d-fabs(r-t.r))<0 || sgn(d-(r+t.r))>0)return res;
if(sgn(d)==0 && sgn(r-t.r)==0)
{
db p=max(a,t.a),q=min(b,t.b);
if(sgn(p-q)<=0)
{
res.push_back(get_point(p));
res.push_back(get_point(q));
}
return res;
}
db h=sqrt(max(0.0L,r*r-pow((r*r+d*d-t.r*t.r)/(2*d),2)));
d=sqrt(max(0.0L,r*r-h*h));
Point v=(t.o-o)/(t.o-o).len();
Point m=o+v*d;
v=Point(-v.y,v.x);
for(int i=-1; i<=1; i+=2)
{
Point p=m+v*h*i;
if(on_circle(p) && t.on_circle(p))
res.push_back(p);
}
return res;
}
friend vector<Point> operator & (const Segment &lhs,const Circle &rhs)
{
return rhs&lhs;
}
friend istream& operator >> (istream &in,Circle &t)
{
in>>t.o>>t.r;
t.a=0,t.b=2*PI;
return in;
}
};
struct Sector
{
Circle c;
Segment l,r;
Sector() {}
Sector(Circle _c)
{
c=_c;
l=Segment(c.o,c.get_point(c.a));
r=Segment(c.get_point(c.b),c.o);
}
db cal_area()const
{
return c.cal_area();
}
db operator & (const Sector &t)const
{
db res=0;
if(sgn(c.r)==0 || sgn(t.c.r)==0)return res;
Sector sec[2]= {*this,t};
for(int i=0; i<2; i++)
{
vector<db> event;
vector<Point> inter;
Segment now[2]= {sec[i].l,sec[i].r};
for(int j=0; j<2; j++)
{
event.clear();
event.push_back(0),event.push_back(1);
inter=now[j]&sec[i^1].l;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
inter=now[j]&sec[i^1].r;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
inter=now[j]&sec[i^1].c;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
sort(event.begin(),event.end());
for(int k=0; k+1<(int)event.size(); k++)
if(sec[i^1].c.in_circle(now[j].get_point((event[k]+event[k+1])/2),i,i,i^1))
res+=now[j].cal_contribution(event[k],event[k+1]);
}
{
event.clear();
event.push_back(sec[i].c.a),event.push_back(sec[i].c.b);
inter=sec[i].c&sec[i^1].l;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
inter=sec[i].c&sec[i^1].r;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
inter=sec[i].c&sec[i^1].c;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
sort(event.begin(),event.end());
for(int k=0; k+1<(int)event.size(); k++)
if(sec[i^1].c.in_circle(sec[i].c.get_point((event[k]+event[k+1])/2),i,i,i^1))
res+=sec[i].c.cal_contribution(event[k],event[k+1]);
}
}
return res;
}
};
vector<int> get_tangent(vector<Point> polygon,Point location)
{
int n=(int)polygon.size();
vector<int> res(2);
for(int i=0; i<2; i++)
res[i]=(sgn(location.x-polygon[0].x)==0 && sgn(location.y-polygon[0].y)==0);
for(int i=0; i<2*n; i++)
{
int id=i%n;
if(sgn((polygon[id]-location)*(polygon[res[0]]-location))<0)res[0]=id;
if(sgn((polygon[id]-location)*(polygon[res[1]]-location))>0)res[1]=id;
}
return res;
}
vector<vector<Point> > split_polygon(vector<Point> polygon,Point location)
{
int n=(int)polygon.size();
vector<int> cut=get_tangent(polygon,location);
vector<Point> first,second;
for(int i=cut[1];; i=(i+1)%n)
{
first.push_back(polygon[i]);
if(i==cut[0])break;
}
for(int i=cut[0];; i=(i+1)%n)
{
second.push_back(polygon[i]);
if(i==cut[1])break;
}
first.push_back(location);
second.push_back(location);
reverse(second.begin(),second.end());
return vector<vector<Point> > {first,second};
}
db get_intersection(vector<Point> polygon,Circle cover)
{
int n=(int)polygon.size();
db res=0;
for(int i=0; i<n; i++)
{
Point a=polygon[i];
Point b=polygon[(i+1)%n];
vector<Point> tmp=Segment(a,b)&cover;
tmp.insert(tmp.begin(),a);
tmp.push_back(b);
for(int j=0; j+1<(int)tmp.size(); j++)
{
if(cover.in_circle((tmp[j]+tmp[j+1])/2))
res+=(tmp[j]-cover.o)*(tmp[j+1]-cover.o);
else
{
db t=(tmp[j]-cover.o).arc(tmp[j+1]-cover.o);
res+=cover.r*cover.r*t*sgn((tmp[j]-cover.o)*(tmp[j+1]-cover.o));
}
}
}
return res/2;
}
void add_sector(vector<Sector> §ors,Circle now)
{
if(sgn(now.a-now.b)<=0)sectors.push_back(Sector(now));
else
{
sectors.push_back(Sector(Circle(now.o,now.r,now.a,2*PI)));
sectors.push_back(Sector(Circle(now.o,now.r,0,now.b)));
}
}
db sum_of_sectors(vector<Point> polygon,db distance)
{
polygon.insert(polygon.begin(),polygon.back());
int n=(int)polygon.size();
vector<Sector> lef,rig;
add_sector(lef,Circle(polygon[0],distance,(polygon[n-2]-polygon[n-1]).arc(),(polygon[1]-polygon[0]).arc()));
add_sector(rig,Circle(polygon[0],distance,(polygon[n-2]-polygon[n-1]).arc(),(polygon[1]-polygon[0]).arc()));
db lef_len=max(0.0L,distance-(polygon[1]-polygon[0]).len()),rig_len=max(0.0L,distance-(polygon[n-2]-polygon[n-1]).len());
int lef_pos=1,rig_pos=n-2;
while(lef_pos+1<rig_pos)
{
if(lef_len>rig_len)
{
add_sector(lef,Circle(polygon[lef_pos],lef_len,(polygon[lef_pos]-polygon[lef_pos-1]).arc(),(polygon[lef_pos+1]-polygon[lef_pos]).arc()));
lef_len=max(0.0L,lef_len-(polygon[lef_pos+1]-polygon[lef_pos]).len()),lef_pos++;
}
else
{
add_sector(rig,Circle(polygon[rig_pos],rig_len,(polygon[rig_pos-1]-polygon[rig_pos]).arc(),(polygon[rig_pos]-polygon[rig_pos+1]).arc()));
rig_len=max(0.0L,rig_len-(polygon[rig_pos-1]-polygon[rig_pos]).len()),rig_pos--;
}
}
add_sector(lef,Circle(polygon[lef_pos],lef_len,(polygon[lef_pos]-polygon[lef_pos-1]).arc(),(polygon[lef_pos+1]-polygon[lef_pos]).arc()));
add_sector(rig,Circle(polygon[rig_pos],rig_len,(polygon[rig_pos-1]-polygon[rig_pos]).arc(),(polygon[rig_pos]-polygon[rig_pos+1]).arc()));
db res=0;
for(int i=0; i<(int)lef.size(); i++)
res+=lef[i].cal_area();
for(int i=0; i<(int)rig.size(); i++)
res+=rig[i].cal_area();
for(int i=0; i<(int)lef.size(); i++)
for(int j=0; j<(int)rig.size(); j++)
res-=lef[i]&rig[j];
return res;
}
db solve(vector<Point> polygon,Circle cover)
{
vector<vector<Point> > tmp=split_polygon(polygon,cover.o);
return get_intersection(tmp[1],cover)+sum_of_sectors(tmp[0],cover.r);
}
int cnt=0;
void Main()
{
cnt++;
int n;
cin>>n;
vector<Point> polygon(n);
for(int i=0; i<n; i++)
cin>>polygon[i];
Circle cover;
cin>>cover;
cout<<solve(polygon,cover)<<endl;
}
int main()
{
int T;
cin>>T;
cout<<fixed<<setprecision(12);
while(T--)Main();
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 273ms, 内存消耗: 500K, 提交时间: 2017-09-06 13:55:46
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
typedef long double db;
const db PI=acos(-1.0);
const db eps=1e-9;
inline int sgn(db x)
{
return (x>eps ? 1 : (x<-eps ? -1 : 0));
}
struct Point
{
db x,y;
Point() {}
Point(db _x,db _y):x(_x),y(_y) {}
Point operator + (const Point &t)const
{
return Point(x+t.x,y+t.y);
}
Point operator - (const Point &t)const
{
return Point(x-t.x,y-t.y);
}
Point operator * (const db &t)const
{
return Point(x*t,y*t);
}
Point operator / (const db &t)const
{
return Point(x/t,y/t);
}
db operator * (const Point &t)const
{
return x*t.y-y*t.x;
}
db operator ^ (const Point &t)const
{
return x*t.x+y*t.y;
}
db len()const
{
return sqrt(x*x+y*y);
}
db arc(const int &on=0)const
{
db t=atan2(y,x);
if(t<(on ? 1 : -1)*eps)t+=2*PI;
return t;
}
db arc(const Point &t)const
{
db r=((*this)^t)/((*this).len()*t.len());
return acos(max(-1.0L,min(1.0L,r)));
}
friend istream& operator >> (istream &in,Point &t)
{
in>>t.x>>t.y;
return in;
}
friend ostream& operator << (ostream &out,const Point &t)
{
out<<"("<<t.x<<","<<t.y<<")";
return out;
}
};
struct Segment
{
Point s,e;
Segment() {}
Segment(Point _s,Point _e):s(_s),e(_e) {}
db get_ratio(const Point &t)const
{
return ((t-s)^(e-s))/((e-s)^(e-s));
}
Point get_point(const db &t)const
{
return s+(e-s)*t;
}
db cal_contribution(const db &a,const db &b)
{
return get_point(a)*get_point(b)/2;
}
bool on_segment(const Point &t)const
{
if(sgn((t-s)*(t-e)))return 0;
db r=get_ratio(t);
return sgn(r)>=0 && sgn(r-1)<=0;
}
vector<Point> operator & (const Segment &t)const
{
vector<Point> res;
if(sgn((e-s)*(t.e-t.s))==0)
{
if(on_segment(t.s))res.push_back(t.s);
if(on_segment(t.e))res.push_back(t.e);
if(t.on_segment(s))res.push_back(s);
if(t.on_segment(e))res.push_back(e);
return res;
}
db r=((t.s-s)*(t.e-t.s))/((e-s)*(t.e-t.s));
Point p=get_point(r);
if(on_segment(p) && t.on_segment(p))
res.push_back(p);
return res;
}
};
struct Circle
{
Point o;
db r,a,b;
Circle() {}
Circle(Point _o,db _r,db _a=0,db _b=2*PI):o(_o),r(_r),a(_a),b(_b) {}
db get_arc(const Point &t)const
{
return (t-o).arc(a>eps);
}
bool in_circle(const Point &t,const int &cir=0,const int &lef=0,const int &rig=0)const
{
db d=(o-t).len();
if(sgn(d-r)>=cir)return 0;
if(sgn(d)==0)return 1;
db s=get_arc(t);
return sgn(s-a)>-lef && sgn(s-b)<rig;
}
bool on_circle(const Point &t)const
{
db d=(o-t).len();
if(sgn(d-r))return 0;
if(sgn(r)==0)return 1;
db s=get_arc(t);
return sgn(s-a)>=0 && sgn(s-b)<=0;
}
Point get_point(const db &t)const
{
return o+Point(cos(t),sin(t))*r;
}
db cal_contribution(const db &a,const db &b)const
{
return (get_point(a)*get_point(b)+r*r*((b-a)-sin(b-a)))/2;
}
db cal_area()const
{
return r*r*(b-a)/2;
}
vector<Point> operator & (const Segment &t)const
{
vector<Point> res;
Point m=t.s+(t.e-t.s)*t.get_ratio(o);
Point v=(t.e-t.s)/(t.e-t.s).len();
db d=(m-o).len();
if(sgn(d-r)>0)return res;
d=sqrt(max(0.0L,r*r-d*d));
for(int i=-1; i<=1; i+=2)
{
Point p=m+v*d*i;
if(on_circle(p) && t.on_segment(p))
res.push_back(p);
}
return res;
}
vector<Point> operator & (const Circle &t)const
{
vector<Point> res;
db d=(o-t.o).len();
if(sgn(d-fabs(r-t.r))<0 || sgn(d-(r+t.r))>0)return res;
if(sgn(d)==0 && sgn(r-t.r)==0)
{
db p=max(a,t.a),q=min(b,t.b);
if(sgn(p-q)<=0)
{
res.push_back(get_point(p));
res.push_back(get_point(q));
}
return res;
}
db h=sqrt(max(0.0L,r*r-pow((r*r+d*d-t.r*t.r)/(2*d),2)));
d=sqrt(max(0.0L,r*r-h*h));
Point v=(t.o-o)/(t.o-o).len();
Point m=o+v*d;
v=Point(-v.y,v.x);
for(int i=-1; i<=1; i+=2)
{
Point p=m+v*h*i;
if(on_circle(p) && t.on_circle(p))
res.push_back(p);
}
return res;
}
friend vector<Point> operator & (const Segment &lhs,const Circle &rhs)
{
return rhs&lhs;
}
friend istream& operator >> (istream &in,Circle &t)
{
in>>t.o>>t.r;
t.a=0,t.b=2*PI;
return in;
}
};
struct Sector
{
Circle c;
Segment l,r;
Sector() {}
Sector(Circle _c)
{
c=_c;
l=Segment(c.o,c.get_point(c.a));
r=Segment(c.get_point(c.b),c.o);
}
db cal_area()const
{
return c.cal_area();
}
db operator & (const Sector &t)const
{
db res=0;
if(sgn(c.r)==0 || sgn(t.c.r)==0)return res;
Sector sec[2]= {*this,t};
for(int i=0; i<2; i++)
{
vector<db> event;
vector<Point> inter;
Segment now[2]= {sec[i].l,sec[i].r};
for(int j=0; j<2; j++)
{
event.clear();
event.push_back(0),event.push_back(1);
inter=now[j]&sec[i^1].l;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
inter=now[j]&sec[i^1].r;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
inter=now[j]&sec[i^1].c;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(now[j].get_ratio(inter[k]));
sort(event.begin(),event.end());
for(int k=0; k+1<(int)event.size(); k++)
if(sec[i^1].c.in_circle(now[j].get_point((event[k]+event[k+1])/2),i,i,i^1))
res+=now[j].cal_contribution(event[k],event[k+1]);
}
{
event.clear();
event.push_back(sec[i].c.a),event.push_back(sec[i].c.b);
inter=sec[i].c&sec[i^1].l;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
inter=sec[i].c&sec[i^1].r;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
inter=sec[i].c&sec[i^1].c;
for(int k=0; k<(int)inter.size(); k++)
event.push_back(sec[i].c.get_arc(inter[k]));
sort(event.begin(),event.end());
for(int k=0; k+1<(int)event.size(); k++)
if(sec[i^1].c.in_circle(sec[i].c.get_point((event[k]+event[k+1])/2),i,i,i^1))
res+=sec[i].c.cal_contribution(event[k],event[k+1]);
}
}
return res;
}
};
vector<int> get_tangent(vector<Point> polygon,Point location)
{
int n=(int)polygon.size();
vector<int> res(2);
for(int i=0; i<2; i++)
res[i]=(sgn(location.x-polygon[0].x)==0 && sgn(location.y-polygon[0].y)==0);
for(int i=0; i<2*n; i++)
{
int id=i%n;
if(sgn((polygon[id]-location)*(polygon[res[0]]-location))<0)res[0]=id;
if(sgn((polygon[id]-location)*(polygon[res[1]]-location))>0)res[1]=id;
}
return res;
}
vector<vector<Point> > split_polygon(vector<Point> polygon,Point location)
{
int n=(int)polygon.size();
vector<int> cut=get_tangent(polygon,location);
vector<Point> first,second;
for(int i=cut[1];; i=(i+1)%n)
{
first.push_back(polygon[i]);
if(i==cut[0])break;
}
for(int i=cut[0];; i=(i+1)%n)
{
second.push_back(polygon[i]);
if(i==cut[1])break;
}
first.push_back(location);
second.push_back(location);
reverse(second.begin(),second.end());
return vector<vector<Point> > {first,second};
}
db get_intersection(vector<Point> polygon,Circle cover)
{
int n=(int)polygon.size();
db res=0;
for(int i=0; i<n; i++)
{
Point a=polygon[i];
Point b=polygon[(i+1)%n];
vector<Point> tmp=Segment(a,b)&cover;
tmp.insert(tmp.begin(),a);
tmp.push_back(b);
for(int j=0; j+1<(int)tmp.size(); j++)
{
if(cover.in_circle((tmp[j]+tmp[j+1])/2))
res+=(tmp[j]-cover.o)*(tmp[j+1]-cover.o);
else
{
db t=(tmp[j]-cover.o).arc(tmp[j+1]-cover.o);
res+=cover.r*cover.r*t*sgn((tmp[j]-cover.o)*(tmp[j+1]-cover.o));
}
}
}
return res/2;
}
void add_sector(vector<Sector> §ors,Circle now)
{
if(sgn(now.a-now.b)<=0)sectors.push_back(Sector(now));
else
{
sectors.push_back(Sector(Circle(now.o,now.r,now.a,2*PI)));
sectors.push_back(Sector(Circle(now.o,now.r,0,now.b)));
}
}
db sum_of_sectors(vector<Point> polygon,db distance)
{
polygon.insert(polygon.begin(),polygon.back());
int n=(int)polygon.size();
vector<Sector> lef,rig;
add_sector(lef,Circle(polygon[0],distance,(polygon[n-2]-polygon[n-1]).arc(),(polygon[1]-polygon[0]).arc()));
add_sector(rig,Circle(polygon[0],distance,(polygon[n-2]-polygon[n-1]).arc(),(polygon[1]-polygon[0]).arc()));
db lef_len=max(0.0L,distance-(polygon[1]-polygon[0]).len()),rig_len=max(0.0L,distance-(polygon[n-2]-polygon[n-1]).len());
int lef_pos=1,rig_pos=n-2;
while(lef_pos+1<rig_pos)
{
if(lef_len>rig_len)
{
add_sector(lef,Circle(polygon[lef_pos],lef_len,(polygon[lef_pos]-polygon[lef_pos-1]).arc(),(polygon[lef_pos+1]-polygon[lef_pos]).arc()));
lef_len=max(0.0L,lef_len-(polygon[lef_pos+1]-polygon[lef_pos]).len()),lef_pos++;
}
else
{
add_sector(rig,Circle(polygon[rig_pos],rig_len,(polygon[rig_pos-1]-polygon[rig_pos]).arc(),(polygon[rig_pos]-polygon[rig_pos+1]).arc()));
rig_len=max(0.0L,rig_len-(polygon[rig_pos-1]-polygon[rig_pos]).len()),rig_pos--;
}
}
add_sector(lef,Circle(polygon[lef_pos],lef_len,(polygon[lef_pos]-polygon[lef_pos-1]).arc(),(polygon[lef_pos+1]-polygon[lef_pos]).arc()));
add_sector(rig,Circle(polygon[rig_pos],rig_len,(polygon[rig_pos-1]-polygon[rig_pos]).arc(),(polygon[rig_pos]-polygon[rig_pos+1]).arc()));
db res=0;
for(int i=0; i<(int)lef.size(); i++)
res+=lef[i].cal_area();
for(int i=0; i<(int)rig.size(); i++)
res+=rig[i].cal_area();
for(int i=0; i<(int)lef.size(); i++)
for(int j=0; j<(int)rig.size(); j++)
res-=lef[i]&rig[j];
return res;
}
db solve(vector<Point> polygon,Circle cover)
{
vector<vector<Point> > tmp=split_polygon(polygon,cover.o);
return get_intersection(tmp[1],cover)+sum_of_sectors(tmp[0],cover.r);
}
int cnt=0;
void Main()
{
cnt++;
int n;
cin>>n;
vector<Point> polygon(n);
for(int i=0; i<n; i++)
cin>>polygon[i];
Circle cover;
cin>>cover;
cout<<solve(polygon,cover)<<endl;
}
int main()
{
int T;
cin>>T;
cout<<fixed<<setprecision(12);
while(T--)Main();
return 0;
}