Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define db double
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const db eps=1e-8;
- const int N=505;
- inline db sqr(db x){
- return x*x;
- }
- inline int dcmp(const db &x){
- if(fabs(x)<eps)return 0;
- return x>0?1:-1;
- }
- struct Point{
- db x,y;
- inline Point(){}
- inline Point(db _x,db _y):x(_x),y(_y){}
- };
- #define Vec Point
- inline Vec operator +(const Vec &a,const Vec &b){
- return Vec(a.x+b.x,a.y+b.y);
- }
- inline Vec operator -(const Vec &a,const Vec &b){
- return Vec(a.x-b.x,a.y-b.y);
- }
- inline void operator +=(Vec &a,const Vec &b){
- a.x+=b.x,a.y+=b.y;
- }
- inline void operator -=(Vec &a,const Vec &b){
- a.x-=b.x,a.y-=b.y;
- }
- inline Vec operator *(const Vec &a,const db &b){
- return Vec(a.x*b,a.y*b);
- }
- inline Vec operator /(const Vec &a,const db &b){
- return Vec(a.x/b,a.y/b);
- }
- inline db Cross(const Vec &a,const Vec &b){
- return a.x*b.y-a.y*b.x;
- }
- inline db Angle(const Vec &a){
- return atan2(a.y,a.x);
- }
- struct Line{
- Point S,T;
- db theta;
- inline Line(){}
- inline Line(const Point &A,const Point &B):S(A),T(B),theta(Angle(B-A)){}
- };
- inline bool OnRight(const Line &a,const Point &A){
- return dcmp(Cross(a.T-a.S,A-a.S))==-1;
- }
- inline bool operator <(const Line &a,const Line &b){
- if(dcmp(a.theta-b.theta))return dcmp(a.theta-b.theta)==-1;
- return dcmp(Cross(a.T-a.S,b.S-a.S))==-1;
- }
- inline Point LineCross(const Line &a,const Line &b){
- Vec u=a.T-a.S;
- Vec v=b.T-b.S;
- Vec w=a.S-b.S;
- db t=Cross(w,v)/Cross(v,u);
- return a.S+u*t;
- }
- Line Q1[N];
- Point Q2[N];
- inline int Half(Line *A,int n,Point *B){
- sort(A+1,A+n+1);
- int head=0,tail=0;
- Q1[0]=A[1];
- for(int i=2;i<=n;++i){
- while(head<tail&&OnRight(A[i],Q2[tail-1]))--tail;
- while(head<tail&&OnRight(A[i],Q2[head]))++head;
- Q1[++tail]=A[i];
- Q2[tail-1]=LineCross(A[i],Q1[tail-1]);
- }
- while(head<tail&&OnRight(Q1[head],Q2[tail-1]))--tail;
- while(head<tail&&OnRight(Q1[head],Q2[head]))++head;
- Q2[tail]=LineCross(Q1[head],Q1[tail]);
- n=0;
- for(int i=head;i<=tail;++i)B[++n]=Q2[i];
- return n;
- }
- inline db Area(Point *A,int n){
- db sum=Cross(A[n],A[1]);
- for(int i=1;i<n;++i){
- sum+=Cross(A[i],A[i+1]);
- }
- return sum/2;
- }
- Point A[N];
- Line B[N];
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n,tot=0;r(n);
- while(n--){
- int m;r(m);
- for(int i=1;i<=m;++i){
- int x,y;r(x),r(y);
- A[i]=Point(x,y);
- }
- for(int i=1;i<m;++i){
- B[++tot]=Line(A[i],A[i+1]);
- }
- B[++tot]=Line(A[m],A[1]);
- }
- n=Half(B,tot,A);
- printf("%.3lf",Area(A,n));
- return 0;
- }
Add Comment
Please, Sign In to add comment