题意：没看懂= =
sol：在纸上随便画两下就可以看出，答案即按逆时针方向建立line，求它们的半平面交的面积。
模板题。注意输出答案时输出ans+eps，否则可能会出现结果为-0.00的情况。
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<complex>
#define mp make_pair
#define pb push_back
using namespace std;
const double eps=1e-;
const double pi=acos(-1.0);
const double inf=1e20;
const int maxp=;
int dblcmp(double d)
{
if (fabs(d)<eps)return ;
return d>eps?:-;
}
inline double sqr(double x){return x*x;}
struct point
{
double x,y;
point(){}
point(double _x,double _y):
x(_x),y(_y){};
void input()
{
scanf("%lf%lf",&x,&y);
}
void output()
{
printf("%.2f %.2f\n",x,y);
}
bool operator==(point a)const
{
return dblcmp(a.x-x)==&&dblcmp(a.y-y)==;
}
bool operator<(point a)const
{
return dblcmp(a.x-x)==?dblcmp(y-a.y)<:x<a.x;
}
double len()
{
return hypot(x,y);
}
double len2()
{
return x*x+y*y;
}
double distance(point p)
{
return hypot(x-p.x,y-p.y);
}
point add(point p)
{
return point(x+p.x,y+p.y);
}
point sub(point p)
{
return point(x-p.x,y-p.y);
}
point mul(double b)
{
return point(x*b,y*b);
}
point div(double b)
{
return point(x/b,y/b);
}
double dot(point p)
{
return x*p.x+y*p.y;
}
double det(point p)
{
return x*p.y-y*p.x;
}
double rad(point a,point b)
{
point p=*this;
return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
}
point trunc(double r)
{
double l=len();
if (!dblcmp(l))return *this;
r/=l;
return point(x*r,y*r);
}
point rotleft()
{
return point(-y,x);
}
point rotright()
{
return point(y,-x);
}
point rotate(point p,double angle)//绕点p逆时针旋转angle角度
{
point v=this->sub(p);
double c=cos(angle),s=sin(angle);
return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
};
struct line
{
point a,b;
line(){}
line(point _a,point _b)
{
a=_a;
b=_b;
}
bool operator==(line v)
{
return (a==v.a)&&(b==v.b);
}
//倾斜角angle
line(point p,double angle)
{
a=p;
if (dblcmp(angle-pi/)==)
{
b=a.add(point(,));
}
else
{
b=a.add(point(,tan(angle)));
}
}
//ax+by+c=0
line(double _a,double _b,double _c)
{
if (dblcmp(_a)==)
{
a=point(,-_c/_b);
b=point(,-_c/_b);
}
else if (dblcmp(_b)==)
{
a=point(-_c/_a,);
b=point(-_c/_a,);
}
else
{
a=point(,-_c/_b);
b=point(,(-_c-_a)/_b);
}
}
void input()
{
a.input();
b.input();
}
void adjust()
{
if (b<a)swap(a,b);
}
double length()
{
return a.distance(b);
}
double angle()//直线倾斜角 0<=angle<180
{
double k=atan2(b.y-a.y,b.x-a.x);
if (dblcmp(k)<)k+=pi;
if (dblcmp(k-pi)==)k-=pi;
return k;
}
//点和线段关系
//1 在逆时针
//2 在顺时针
//3 平行
int relation(point p)
{
int c=dblcmp(p.sub(a).det(b.sub(a)));
if (c<)return ;
if (c>)return ;
return ;
}
bool pointonseg(point p)
{
return dblcmp(p.sub(a).det(b.sub(a)))==&&dblcmp(p.sub(a).dot(p.sub(b)))<=;
}
bool parallel(line v)
{
return dblcmp(b.sub(a).det(v.b.sub(v.a)))==;
}
//2 规范相交
//1 非规范相交
//0 不相交
int segcrossseg(line v)
{
int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
if ((d1^d2)==-&&(d3^d4)==-)return ;
return (d1==&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=||
d2==&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=||
d3==&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=||
d4==&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=);
}
int linecrossseg(line v)//*this seg v line
{
int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
if ((d1^d2)==-)return ;
return (d1==||d2==);
}
//0 平行
//1 重合
//2 相交
int linecrossline(line v)
{
if ((*this).parallel(v))
{
return v.relation(a)==;
}
return ;
}
point crosspoint(line v)
{
double a1=v.b.sub(v.a).det(a.sub(v.a));
double a2=v.b.sub(v.a).det(b.sub(v.a));
return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
}
double dispointtoline(point p)
{
return fabs(p.sub(a).det(b.sub(a)))/length();
}
double dispointtoseg(point p)
{
if (dblcmp(p.sub(b).dot(a.sub(b)))<||dblcmp(p.sub(a).dot(b.sub(a)))<)
{
return min(p.distance(a),p.distance(b));
}
return dispointtoline(p);
}
point lineprog(point p)
{
return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
}
point symmetrypoint(point p)
{
point q=lineprog(p);
return point(*q.x-p.x,*q.y-p.y);
}
}; struct Vector:public point
{
Vector(){}
Vector(double a,double b)
{
x=a; y=b;
}
Vector(point _a,point _b) //a->b
{
double dx=_b.x-_a.x;
double dy=_b.y-_a.y;
x=dx; y=dy;
}
Vector(line v)
{
double dx=v.b.x-v.a.x;
double dy=v.b.y-v.a.y;
x=dx; y=dy;
}
double length()
{
return (sqrt(x*x+y*y));
}
Vector Normal()
{
double L=sqrt(x*x+y*y);
Vector Vans=Vector(-y/L,x/L);
return Vans;
}
}; struct halfplane:public line //半平面
{
double angle;
halfplane(){}
//表示向量 a->b逆时针(左侧)的半平面
halfplane(point _a,point _b)
{
a=_a;
b=_b;
}
halfplane(line v)
{
a=v.a;
b=v.b;
}
void calcangle()
{
angle=atan2(b.y-a.y,b.x-a.x);
}
bool operator<(const halfplane &b)const
{
return angle<b.angle;
}
}; struct polygon
{
int n;
point p[maxp];
line l[maxp];
void input()
{
n=;
for (int i=;i<n;i++)
{
p[i].input();
}
}
void add(point q)
{
p[n++]=q;
}
void getline()
{
for (int i=;i<n;i++)
{
l[i]=line(p[i],p[(i+)%n]);
}
}
struct cmp
{
point p;
cmp(const point &p0){p=p0;}
bool operator()(const point &aa,const point &bb)
{
point a=aa,b=bb;
int d=dblcmp(a.sub(p).det(b.sub(p)));
if (d==)
{
return dblcmp(a.distance(p)-b.distance(p))<;
}
return d>;
}
};
void norm()
{
point mi=p[];
for (int i=;i<n;i++)mi=min(mi,p[i]);
sort(p,p+n,cmp(mi));
}
void getconvex(polygon &convex)
{
int i,j,k;
sort(p,p+n);
convex.n=n;
for (i=;i<min(n,);i++)
{
convex.p[i]=p[i];
}
if (n<=)return;
int &top=convex.n;
top=;
for (i=;i<n;i++)
{
while (top&&convex.p[top].sub(p[i]).det(convex.p[top-].sub(p[i]))<=)
top--;
convex.p[++top]=p[i];
}
int temp=top;
convex.p[++top]=p[n-];
for (i=n-;i>=;i--)
{
while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-].sub(p[i]))<=)
top--;
convex.p[++top]=p[i];
}
}
bool isconvex()
{
bool s[];
memset(s,,sizeof(s));
int i,j,k;
for (i=;i<n;i++)
{
j=(i+)%n;
k=(j+)%n;
s[dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])))+]=;
if (s[]&&s[])return ;
}
return ;
}
//3 点上
//2 边上
//1 内部
//0 外部
int relationpoint(point q)
{
int i,j;
for (i=;i<n;i++)
{
if (p[i]==q)return ;
}
getline();
for (i=;i<n;i++)
{
if (l[i].pointonseg(q))return ;
}
int cnt=;
for (i=;i<n;i++)
{
j=(i+)%n;
int k=dblcmp(q.sub(p[j]).det(p[i].sub(p[j])));
int u=dblcmp(p[i].y-q.y);
int v=dblcmp(p[j].y-q.y);
if (k>&&u<&&v>=)cnt++;
if (k<&&v<&&u>=)cnt--;
}
return cnt!=;
}
//1 在多边形内长度为正
//2 相交或与边平行
//0 无任何交点
int relationline(line u)
{
int i,j,k=;
getline();
for (i=;i<n;i++)
{
if (l[i].segcrossseg(u)==)return ;
if (l[i].segcrossseg(u)==)k=;
}
if (!k)return ;
vector<point>vp;
for (i=;i<n;i++)
{
if (l[i].segcrossseg(u))
{
if (l[i].parallel(u))
{
vp.pb(u.a);
vp.pb(u.b);
vp.pb(l[i].a);
vp.pb(l[i].b);
continue;
}
vp.pb(l[i].crosspoint(u));
}
}
sort(vp.begin(),vp.end());
int sz=vp.size();
for (i=;i<sz-;i++)
{
point mid=vp[i].add(vp[i+]).div();
if (relationpoint(mid)==)return ;
}
return ;
}
//直线u切割凸多边形左侧
//注意直线方向
void convexcut(line u,polygon &po)
{
int i,j,k;
int &top=po.n;
top=;
for (i=;i<n;i++)
{
int d1=dblcmp(p[i].sub(u.a).det(u.b.sub(u.a)));
int d2=dblcmp(p[(i+)%n].sub(u.a).det(u.b.sub(u.a)));
if (d1>=)po.p[top++]=p[i];
if (d1*d2<)po.p[top++]=u.crosspoint(line(p[i],p[(i+)%n]));
}
}
double getcircumference()
{
double sum=;
int i;
for (i=;i<n;i++)
{
sum+=p[i].distance(p[(i+)%n]);
}
return sum;
}
double getarea()
{
double sum=;
int i;
for (i=;i<n;i++)
{
sum+=p[i].det(p[(i+)%n]);
}
return fabs(sum)/;
}
bool getdir()//1代表逆时针 0代表顺时针
{
double sum=;
int i;
for (i=;i<n;i++)
{
sum+=p[i].det(p[(i+)%n]);
}
if (dblcmp(sum)>)return ;
return ;
}
point getbarycentre()
{
point ret(,);
double area=;
int i;
for (i=;i<n-;i++)
{
double tmp=p[i].sub(p[]).det(p[i+].sub(p[]));
if (dblcmp(tmp)==)continue;
area+=tmp;
ret.x+=(p[].x+p[i].x+p[i+].x)/*tmp;
ret.y+=(p[].y+p[i].y+p[i+].y)/*tmp;
}
if (dblcmp(area))ret=ret.div(area);
return ret;
}
double areaintersection(polygon po)
{
}
double areaunion(polygon po)
{
return getarea()+po.getarea()-areaintersection(po);
}
/*
double areacircle(circle c)
{
int i,j,k,l,m;
double ans=0;
for (i=0;i<n;i++)
{
int j=(i+1)%n;
if (dblcmp(p[j].sub(c.p).det(p[i].sub(c.p)))>=0)
{
ans+=c.areatriangle(p[i],p[j]);
}
else
{
ans-=c.areatriangle(p[i],p[j]);
}
}
return fabs(ans);
}
//多边形和圆关系
//0 一部分在圆外
//1 与圆某条边相切
//2 完全在圆内
int relationcircle(circle c)
{
getline();
int i,x=2;
if (relationpoint(c.p)!=1)return 0;
for (i=0;i<n;i++)
{
if (c.relationseg(l[i])==2)return 0;
if (c.relationseg(l[i])==1)x=1;
}
return x;
}
void find(int st,point tri[],circle &c)
{
if (!st)
{
c=circle(point(0,0),-2);
}
if (st==1)
{
c=circle(tri[0],0);
}
if (st==2)
{
c=circle(tri[0].add(tri[1]).div(2),tri[0].distance(tri[1])/2.0);
}
if (st==3)
{
c=circle(tri[0],tri[1],tri[2]);
}
}
void solve(int cur,int st,point tri[],circle &c)
{
find(st,tri,c);
if (st==3)return;
int i;
for (i=0;i<cur;i++)
{
if (dblcmp(p[i].distance(c.p)-c.r)>0)
{
tri[st]=p[i];
solve(i,st+1,tri,c);
}
}
}
circle mincircle()//点集最小圆覆盖
{
random_shuffle(p,p+n);
point tri[4];
circle c;
solve(n,0,tri,c);
return c;
}
int circlecover(double r)//单位圆覆盖
{
int ans=0,i,j;
vector<pair<double,int> >v;
for (i=0;i<n;i++)
{
v.clear();
for (j=0;j<n;j++)if (i!=j)
{
point q=p[i].sub(p[j]);
double d=q.len();
if (dblcmp(d-2*r)<=0)
{
double arg=atan2(q.y,q.x);
if (dblcmp(arg)<0)arg+=2*pi;
double t=acos(d/(2*r));
v.push_back(make_pair(arg-t+2*pi,-1));
v.push_back(make_pair(arg+t+2*pi,1));
}
}
sort(v.begin(),v.end());
int cur=0;
for (j=0;j<v.size();j++)
{
if (v[j].second==-1)++cur;
else --cur;
ans=max(ans,cur);
}
}
return ans+1;
}
*/
int pointinpolygon(point q)//点在凸多边形内部的判定
{
if (getdir())reverse(p,p+n);
if (dblcmp(q.sub(p[]).det(p[n-].sub(p[])))==)
{
if (line(p[n-],p[]).pointonseg(q))return n-;
return -;
}
int low=,high=n-,mid;
while (low<=high)
{
mid=(low+high)>>;
if (dblcmp(q.sub(p[]).det(p[mid].sub(p[])))>=&&dblcmp(q.sub(p[]).det(p[mid+].sub(p[])))<)
{
polygon c;
c.p[]=p[mid];
c.p[]=p[mid+];
c.p[]=p[];
c.n=;
if (c.relationpoint(q))return mid;
return -;
}
if (dblcmp(q.sub(p[]).det(p[mid].sub(p[])))>)
{
low=mid+;
}
else
{
high=mid-;
}
}
return -;
}
}; struct halfplanes //半平面交
{
int n;
halfplane hp[maxp];
point p[maxp];
int que[maxp];
int st,ed;
void push(halfplane tmp)
{
hp[n++]=tmp;
}
void unique()
{
int m=,i;
for (i=;i<n;i++)
{
if (dblcmp(hp[i].angle-hp[i-].angle))hp[m++]=hp[i];
else if (dblcmp(hp[m-].b.sub(hp[m-].a).det(hp[i].a.sub(hp[m-].a))>))hp[m-]=hp[i];
}
n=m;
}
bool halfplaneinsert()
{
int i;
for (i=;i<n;i++)hp[i].calcangle();
sort(hp,hp+n);
unique();
que[st=]=;
que[ed=]=;
p[]=hp[].crosspoint(hp[]);
for (i=;i<n;i++)
{
while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[ed].sub(hp[i].a))))<)ed--;
while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[st+].sub(hp[i].a))))<)st++;
que[++ed]=i;
if (hp[i].parallel(hp[que[ed-]]))return false;
p[ed]=hp[i].crosspoint(hp[que[ed-]]);
}
while (st<ed&&dblcmp(hp[que[st]].b.sub(hp[que[st]].a).det(p[ed].sub(hp[que[st]].a)))<)ed--;
while (st<ed&&dblcmp(hp[que[ed]].b.sub(hp[que[ed]].a).det(p[st+].sub(hp[que[ed]].a)))<)st++;
if (st+>=ed)return false;
return true;
}
void getconvex(polygon &con)
{
p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
con.n=ed-st+;
int j=st,i=;
for (;j<=ed;i++,j++)
{
con.p[i]=p[j];
}
}
}; point p[];
halfplanes TH;
int n,T; int main()
{
//freopen("in.txt","r",stdin); cin>>T;
while (T--)
{
cin>>n;
for (int i=n-;i>=;i--)
p[i].input();
//p[i]->p[i+1] TH.n=;
for (int i=;i<=n-;i++)
TH.push(halfplane(p[i],p[(i+)%n])); double ans=0.00;
if (TH.halfplaneinsert())
{
polygon Gans;
TH.getconvex(Gans);
ans=Gans.getarea();
}
printf("%.2lf\n",ans+eps);
} return ;
}