%%%
by zbr2006 @ 2020-07-07 20:53:30
计几神仙tql
by AC_Dolphin @ 2020-07-07 21:09:16
Line 的 $p_1$ 是一个定点 $p_2$ 是向量qaq
by Demoe @ 2020-07-07 21:10:17
@[Daniel_Jiang](/user/83999) ~~建议整份发上来~~
by ez_lcw @ 2020-07-07 21:19:24
@[ez_lcw](/user/118318) 长长长长（
有些没用的函数也放进来了/kel
```cpp
/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T> void rd(T &x){
ll fl=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
x*=fl;
}
void wr(ll x){
if(x<0) x=-x,putchar('-');
if(x<10) putchar(x+'0');
if(x>9) wr(x/10),putchar(x%10+'0');
}
const double pi=acos(-1.0),eps=1e-8;
ll sgn(double x){ //判断是否为0
if(fabs(x)<eps) return 0;
return x<0.0?-1:1;
}
ll dcmp(double x,double y){ //比较浮点数大小
if(fabs(x-y)<eps) return 0;
return x<y?-1:1;
}
struct Point{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator + (Point A){return Point(x+A.x,y+A.y);}
Point operator - (Point A){return Point(x-A.x,y-A.y);}
Point operator * (double k){return Point(x*k,y*k);}
Point operator / (double k){return Point(x*k,y*k);}
bool operator == (Point A){return sgn(x-A.x)==0&&sgn(y-A.y)==0;}
bool operator < (Point A){return sgn(x-A.x)<0||sgn(x-A.x)==0&&sgn(y-A.y)<0;} //用于凸包计算比较两点
};
typedef Point Vector;
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;} //点积
double Len2(Vector A){return Dot(A,A);}
double Len(Vector A){return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));} //AB夹角
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} //叉积
double Area(Point A,Point B,Point C){return Cross(B-A,C-A);} //ABC三点形成三角形面积
double Dist(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));} //两点间距离
Vector Normal(Vector A){return Vector(-A.y/Len(A),-A.x/Len(A));} //向量的法向量
bool Parallel(Vector A,Vector B){return sgn(Cross(A,B))==0;} //平行/重合
Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));} //向量逆时针旋转rad度
struct Line{
Point p1,p2;
double ang;
Line(){}
Line(Point p1,Point p2):p1(p1),p2(p2){}
Line(Point p,double angle){
p1=p;
if(sgn(angle-pi/2)==0){p2=p1+Point(0,1);}
else{p2=p1+Point(1,tan(angle));}
}
Line(double a,double b,double c){
if(sgn(a)==0){
p1=Point(0,-c/b);
p2=Point(1,-c/b);
}
else if(sgn(b)==0){
p1=Point(-c/a,0);
p2=Point(-c/a,1);
}
else{
p1=Point(0,-c/b);
p2=Point(1,(-c-a)/b);
}
}
bool operator < (Line v){return ang<v.ang;}
};
typedef Line Segment;
double Line_angle(Line a){
double k=atan2(a.p2.y-a.p1.y,a.p2.x-a.p1.x);
if(sgn(k)<0) k+=pi;
if(sgn(k-pi)==0) k-=pi;
return k;
} //直线倾角
ll Point_line_relation(Point p,Line v){
ll c=sgn(Cross(p-v.p1,v.p2-v.p1));
if(c<0) return 1;
if(c>0) return 2;
return 0;
} //点和直线的关系 1 点在左边 2 点在右边 0 点在直线上
bool Point_on_seg(Point p,Line v){
return sgn(Cross(p-v.p1,v.p2-v.p1))==0&&sgn(Dot(p-v.p1,p-v.p2))<=0;
} //点和线段的关系 0 不在线段上 1 在线段上
ll Line_relation(Line v1,Line v2){
if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1))==0){
if(Point_line_relation(v1.p1,v2)==0) return 1;
return 0;
}
return 2;
} //两直线间的关系 0 平行 1 重合 2 相交
double Dis_point_line(Point p,Line v){return fabs(Cross(p-v.p1,v.p2-v.p1))/Dist(v.p1,v.p2);} //点到直线的距离
Point Point_line_proj(Point p,Line v){
double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
return v.p1+(v.p2-v.p1)*k;
} //点在直线上的投影
Point Point_line_symmetry(Point p,Line v){
Point q=Point_line_proj(p,v);
return Point(2*q.x-p.x,2*q.y-p.y);
} //点关于直线的对称点
double Dis_point_seg(Point p,Segment v){
if(sgn(Dot(p-v.p1,v.p2-v.p1))<0||sgn(Dot(p-v.p2,v.p1-v.p2))<0) return min(Dist(p,v.p1),Dist(p,v.p2));
return Dis_point_line(p,v);
} //点到线段的距离
Point Cross_point(Point a,Point b,Point c,Point d){
double s1=Cross(b-a,c-a),s2=Cross(b-a,d-a);
return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
} //两直线ab和cd的交点 （调用前需保证两直线不平行或重合
bool Cross_segment(Point a,Point b,Point c,Point d){return sgn(Cross(b-a,c-a))*sgn(Cross(b-a,d-a))<0&&sgn(Cross(d-c,a-c))*sgn(Cross(d-c,b-c))<0;} //两线段是否相交 1 相交 0 相离 （交点为端点不含
// ————————多边形qwq————————
const ll maxp=1e5+5;
struct Polygon{
ll n; //顶点数
Point p[maxp];
Line v[maxp];
};
ll Point_in_polygon(Point pt,Point *p,ll n){
for(ll i=0;i<n;i++) if(p[i]==pt) return 3;
for(ll i=0;i<n;i++) if(Point_on_seg(pt,Line(p[i],p[(i+1)%n]))) return 2;
ll num=0;
for(ll i=0;i<n;i++){
ll j=(i+1)%n,c=sgn(Cross(pt-p[j],p[i]-p[j])),u=sgn(p[i].y-pt.y),v=sgn(p[j].y-pt.y);
if(c>0&&u<0&&v>=0) num++;
if(c<0&&u>=0&&v<0) num--;
}
return num!=0;
} //判断点和任意多边形的关系 0 外部 1 内部 2 边上 3 点上
double Polygon_area(Point *p,ll n){
double area=0;
for(ll i=0;i<n;i++) area+=Cross(p[i],p[(i+1)%n]);
return area/2;
} //多边形面积 (面积正负不能直接取绝对值
Point Polygon_center(Point *p,ll n){
Point ans(0,0);
if(Polygon_area(p,n)==0) return ans;
for(ll i=0;i<n;i++) ans=ans+(p[i]+p[(i+1)%n])*Cross(p[i],p[(i+1)%n]);
return ans/Polygon_area(p,n)/6;
} //多边形重心
ll Convex_hull(Point *p,ll n,Point *ch){
sort(p,p+n);
n=unique(p,p+n)-p;
ll v=0;
for(ll i=0;i<n;i++){
while(v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--;
ch[v++]=p[i];
}
ll j=v;
for(ll i=n-2;i>=0;i--){
while(v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--;
ch[v++]=p[i];
}
if(n>1) v--;
return v;
} //二维凸包 返回点个数 ch为点集
double Rotating_calipers(Point *p,ll n,Point *a){
//不要排序不要排序不要排序
double ans=0;
for(ll i=0,j=1;i<n;i++){
while(sgn(Cross(p[(i+1)%n]-p[i],p[j]-p[i])-Cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[i]))<0) j=(j+1)%n;
if(dcmp(ans,Dist(p[j],p[i]))<0) ans=Dist(p[j],p[i]),a[0]=p[i],a[1]=p[j];
if(dcmp(ans,Dist(p[j],p[(i+1)%n]))<0) ans=Dist(p[j],p[(i+1)%n]),a[0]=p[(i+1)%n],a[1]=p[j];
}
return ans;
} //旋转卡壳
bool Onleft(Line v,Point p){return sgn(Cross(v.p2,p-v.p1))>0;} //判断点在直线左边
Point Cross_P(Line a,Line b){
Vector u=a.p1-b.p1;
return a.p1+a.p2*Cross(b.p2,u)/Cross(a.p2,b.p2);
} //半平面交用两直线交点
Polygon HPI(Line *v,ll n){
for(ll i=0;i<n;i++) v[i].ang=Line_angle(v[i]);
sort(v,v+n);
Polygon ans;
Line q[maxp];
Point p[maxp];
ll l=0,r=0;
q[0]=v[0];
for(ll i=1;i<n;i++){
while(l<r&&!Onleft(v[i],p[r-1])) r--;
while(l<r&&!Onleft(v[i],p[l])) l++;
q[++l]=v[i];
if(sgn(Cross(q[r].p2,q[l-1].p2))==0){
r--;
if(Onleft(q[r],v[i].p1)) q[r]=v[i];
}
if(l<r) p[r-1]=Cross_point(q[r-1].p1,q[r-1].p2+q[r-1].p1,q[r].p1,q[r].p2+q[r].p1);
}
while(l<r&&!Onleft(q[l],p[r-1])) r--;
if(r-l<=1) return ans;
p[r]=Cross_point(q[r].p1,q[r].p2+q[r].p1,q[l].p1,q[l].p2+q[l].p1);
for(ll i=l;i<=r;i++) ans.p[i-l]=p[i];
ans.n=r-l+1;
return ans;
}
ll n,cnt;
Polygon a;
Point ans[maxp];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cout<<"-----"<<endl;
rd(n);
for(ll i=0;i<n;i++){
ll m=0;
rd(m);
for(ll j=0;j<m;j++) scanf("%lf %lf",&a.p[j].x,&a.p[j].y);
for(ll j=0;j<m;j++) a.v[cnt+j].p1=a.p[j],a.v[cnt+j].p2=a.p[(j+1)%m]-a.p[j];
cnt+=m;
}
a.v[cnt].p1=Point(0,0),a.v[cnt].p2=Point(0,-1);
a.v[cnt+1].p1=Point(0,0x3f3f3f3f),a.v[cnt+1].p2=Point(-1,0);
cnt+=2;
Polygon an=HPI(a.v,cnt);
double sum=Polygon_area(an.p,an.n);
cout<<fixed<<setprecision(3)<<fabs(sum);puts("");
return 0;
}
```
by Demoe @ 2020-07-08 09:12:53
星 angle忘调了 改一下（（（
还是不行/kk
by Demoe @ 2020-07-08 17:09:47