wa最后一个点,且与答案差别在小数点后第二位qaq
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define re register int
#define in inline
#define eps 1e-8
#define maxn 500005
using namespace std;
in int read()
{
int ans=0,f=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) ans=ans*10+ch-'0';
return ans*f;
}
struct Point{
double x,y;
Point(double x,double y){
this->x=x;
this->y=y;
}
in double Length(){
return sqrt(x*x+y*y);
}
Point(){};
}p[maxn],bao[maxn*2];
int en;
const double pi=acos(-1.0);
typedef Point Vector;
int dcmp(double x)
{
return fabs(x)<eps?0:(x<0?-1:1);
}
in bool operator ==(Point a,Point b)
{
if(dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0) return 1;
return 0;
}
in Vector operator +(Vector a,Vector b)
{
return Vector(a.x+b.x,a.y+b.y);
}
in Vector operator -(Vector a,Vector b)
{
return Vector(a.x-b.x,a.y-b.y);
}
in Vector operator *(Vector a,double b)
{
return Vector(a.x*b,a.y*b);
}
in Vector Unit(Vector a)
{
return a*(1/a.Length());
}
in double dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
in double cross(Vector a,Vector b)//如果 a 在 b 的左侧 那么a 在b 的右侧
{
return a.x*b.y-a.y*b.x;
}
in Vector rotate(Vector a,double rad)//向量逆时针旋转 rad 弧度
{
return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
in Point banana(Point p,Vector v,Point q,Vector w)//交点
{
return p+v*(cross(w,p-q)/cross(v,w));
}
in double DisToLine(Point p,Point a,Point b)//直线上两点 a,b 直线外一点 p
{
Vector v1=b-a,v2=p-a;
return fabs(cross(v1,v2))/v1.Length();
}
in double DisToSegment(Point p,Point a,Point b)//线段 a,b 外一点 到ab 的距离
{
Vector v1=b-a,v2=p-a,v3=p-b;
if(dot(v1,v2)<eps) return v2.Length();
if(dot(v1,v3)>eps) return v3.Length();
return fabs(cross(v1,v2))/v1.Length();
}
in Point GetLineProjection(Point p,Point a,Point b)//点 p 在 ab直线上的投影
{
Vector v=b-a;
return a+v*(dot(v,p-a)/dot(v,v));
}
in bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)//规范相交
{
double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
double c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(Point p,Point a1,Point a2)//一个点是否在线段上
{
if(p==a1||p==a2) return 1;
return fabs(cross(a1-p,a2-p))<eps&&dot(a1-p,a2-p)<-eps;
}
in double polyonarea(Point p[],int n)//多边形的面积
{
double area=0;
for(int i=1;i<n-1;i++) area+=cross(p[i]-p[0],p[i+1]-p[0]);
return area/2.0;
}
in bool cmp(const Point & a,const Point & b)
{
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
in double dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
in void tubao()//凸包 上下凸壳
{
int n;
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
en=0;
sort(p+1,p+1+n,cmp);
for(i=1;i<=n;i++){
while(en>1&&cross(bao[en]-bao[en-1],p[i]-bao[en])<=0) en--;
bao[++en]=p[i];
}
int half=en;
for(i=n-1;i;i--){
while(en>half&&cross(bao[en]-bao[en-1],p[i]-bao[en])<=0) en--;
bao[++en]=p[i];
}
en--;
double ans=0;
for(i=2;i<=en;i++) ans+=dis(bao[i],bao[i-1]);
printf("%.2lf\n",ans+dis(bao[1],bao[en]));
}
in int quare(Vector a)
{
if(a.x>0&&a.y>=0) return 1;
if(a.x<=0&&a.y>0) return 2;
if(a.x<0&&a.y<=0) return 3;
if(a.x>=0&&a.y<0) return 4;
}
bool operator <(Vector a,Vector b)
{
if(quare(a)!=quare(b))
return quare(a)<quare(b);
return cross(a,b)>0;
}
bool same_dir(Vector a,Vector b)
{
return (quare(a)==quare(b))&&(dcmp(cross(a,b))==0);
}
struct Line{
Point p;
Vector v;
double ang;
Line(){}
Line(const Point &a,const Point &b){
v=b-a;
p=a;
ang=atan2(v.y,v.x);//向量的极角 纵在前 横在后
if(ang<0) ang+=2.0*pi;
}
}a[maxn];
in Point banana(Line x,Line y)//交点
{
return banana(x.p,x.v,y.p,y.v);
}
bool operator <(Line x,Line y)
{
//return x.v<y.v;
if(quare(x.v)==quare(y.v)&&fabs(cross(x.v,y.v))<eps) return cross(x.v,x.p+x.v-y.p)>0;
else return x.v<y.v;
}
Point b[maxn],c[maxn];
int n,tot,cnt,num;
Line dui[maxn];
int front,rear;
in int PointPostoLine(Point x,Line y)
{
return cross(y.v,x-y.p);
}
in double f(double x)//待求函数
{
return -x;
}
in double area(double l,double r)
{
return (r-l)/6.0*(f(l)+4.0*f((l+r)/2.0)+f(r));
}
in double sinp(double l,double r)//自适应辛普森积分法
{
double m=(l+r)*0.5;
double t2=area(l,r),t3=area(l,m)+area(m,r);
if(fabs(t2-t3)<eps) return t2;
return sinp(l,m)+sinp(m,r);
}
in Point getcircle(Point i,Point j,Point k)
{
double a,b,c,d,e,f;
a=i.x-j.x;
b=i.y-j.y;
c=i.x-j.x;
d=i.y-j.y;
e=((i.x*i.x-j.x*j.x)-(j.y*j.y-i.y*i.y))/2;
f=((i.x*i.x-k.x*k.x)-(k.y*k.y-i.y*i.y))/2;
Point as;
as.x=-(d*e-b*f)/(b*c-a*d);
as.y=-(a*f-c*e)/(b*c-a*d);
return as;
}
int main()
{
n=read();
re i,j;
int m;
for(i=1;i<=n;i++){
m=read();
for(j=1;j<=m;j++){
b[j].x=read(),b[j].y=read();
}
for(j=1;j<m;j++){
a[++cnt].p=b[j];
a[cnt].v=b[j+1]-b[j];
}
a[++cnt].p=b[m];
a[cnt].v=b[1]-b[m];
}
sort(a+1,a+1+cnt);
front=1,rear=0;
for(i=1;i<=cnt;i++){
while(front<rear&&PointPostoLine(banana(dui[rear],dui[rear-1]),a[i])<0) rear--;
while(front<rear&&PointPostoLine(banana(dui[front],dui[front+1]),a[i])<0) front++;
dui[++rear]=a[i];
}
while(front<rear&&PointPostoLine(banana(dui[rear],dui[rear-1]),dui[front])<0) rear--;
while(front<rear&&PointPostoLine(banana(dui[front],dui[front+1]),dui[rear])<0) front++;
if(rear-front<=1){
printf("0.000");
return 0;
}
for(i=front;i<rear;i++){
c[num++]=banana(dui[i],dui[i+1]);
}
if(!(banana(dui[rear],dui[front])==c[0]))
c[num++]=banana(dui[rear],dui[front]);
printf("%.3lf\n",polyonarea(c,num));
return 0;
}
/*
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0
2
3
0 0
2 0
0 3
4
1 1
3 1
3 3
1 3
*/