1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 #include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33     freopen("data.in","rb",stdin); 34     freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 const int M=10000; 38  39 struct tree 40 { 41     int left,right;//左右区间 42     double turel,turer,cnt;//记录左右区间的真实值和 投影Y轴坐标的覆盖的程度cnt 43     int lbd,rbd;  //辅助求投影Y轴有几段 44     int setline;  //记录投影Y轴有几段，假如[1,2][4,5]覆盖在Y轴 45                  //说明有两段覆盖在Y轴所以该周长应该是nowline+2（Setline）*2*(line[i].x-line[i-1].x) 46     int c; //记录该区间被覆盖几次。 47  48 } node[M*4]; 49 struct Line 50 { 51     double x,y1,y2; //记录每一条扫描线 52     int f;//标记入边1，出边为-1 53 } line[M];//储存所有的线段 54 int cnt; 55 double y[M];//将y的坐标记录然后离散化 56 bool cmp(Line a,Line b)//排序  57 { 58     if (a.x==b.x)  //这句需要有做完该题你会发现有重边的样例过不去， 59                    //排序的时候若X某条出边和某条坐标相等将入边排在前面就能解决重边的问题。 60         return a.f>b.f; 61     return a.x<b.x; 62 } 63 void build__tree(int id,int l,int r)//初始化树 64 { 65     int mid=(l+r)/2; 66     node[id].turel=y[l]; 67     node[id].turer=y[r]; 68     node[id].left=l; 69     node[id].right=r; 70     node[id].cnt=0; 71     node[id].c=0; 72     node[id].lbd=0; 73     node[id].rbd=0; 74     node[id].setline=0; 75     if (l+1==r) 76         return ; 77     build__tree(id*2,l,mid); 78     build__tree(id*2+1,mid,r); 79 } 80 //更新line 81 void upline(int i) 82 { 83     if (node[i].c>0) 84     { 85         node[i].lbd=1; 86         node[i].rbd=1; 87         node[i].setline=1; 88     } 89     else if (node[i].right-node[i].left == 1) 90     { 91         node[i].lbd = 0; 92         node[i].rbd = 0; 93         node[i].setline = 0; 94     } 95     else 96     { 97         node[i].lbd = node[2*i].lbd; 98         node[i].rbd = node[2*i+1].rbd; 99         node[i].setline = node[2*i].setline+node[2*i+1].setline-node[2*i].rbd*node[2*i+1].lbd;100     }101 }102 //更新投影Y轴的线段103 void upcnt(int id)104 {105     if (node[id].c>0)106     {107         node[id].cnt=node[id].turer-node[id].turel;108         return ;109     }110     if (node[id].left+1==node[id].right)111         node[id].cnt=0;112     else113         node[id].cnt=node[id*2].cnt+node[id*2+1].cnt;114 }115 void updata(int id,Line v)116 {117     if (node[id].turel==v.y1&&node[id].turer==v.y2)118     {119         node[id].c+=v.f;120         upcnt(id);121         upline(id);122         return ;123     }124     if (v.y2<=node[id*2].turer)125         updata(id*2,v);126     else if (v.y1>=node[id*2+1].turel)127         updata(id*2+1,v);128     else129     {130         Line tmp;131         tmp=v;132         tmp.y2=node[id*2].turer;133         updata(id*2,tmp);134         tmp=v;135         tmp.y1=node[id*2+1].turel;136         updata(id*2+1,tmp);137     }138     upcnt(id);139     upline(id);140 }141 int main()142 {143     int n;144     scanf("%d",&n);145     int i,j;146     int d=1;147     for(i=1; i<=n; i++)148     {149         double x1,x2,y1,y2;150         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);151         line[d].x=x1;152         line[d].y1=y1;153         line[d].y2=y2;154         line[d].f=1;155         y[d]=y1;156         d++;157         line[d].x=x2;158         line[d].y1=y1;159         line[d].y2=y2;160         line[d].f=-1;161         y[d]=y2;162         d++;163     }164     sort(y+1,y+d);165     sort(line+1,line+d,cmp);166     int ncount=unique(y+1,y+d)-(y+1); //去重。167     build__tree(1,1,ncount);168     updata(1,line[1]);169     double sum=0;170     double ce=0;171     double nowline=0;172     int Setline=0;173     for(i=2; i<d; i++)174     {175         Setline=node[1].setline;176         nowline=node[1].cnt-ce;177         if (nowline<0)178             nowline=-nowline;179         if (node[1].cnt==0)180         {181             sum+=(line[i-1].y2-line[i-1].y1);182             ce=0;183             nowline=0;184         }185         else186             sum+=nowline+Setline*2*(line[i].x-line[i-1].x);187         ce=node[1].cnt;188         updata(1,line[i]);189     }190     sum+=(line[i-1].y2-line[i-1].y1);191     printf("%.0f\n",sum);192     return 0;193 }194 /*195 4196 5 5 20 10197 10 0 15 15198 5 5 30 10199 27 8 35 15200 201 2202 -10 -10 0 10203 0 -10 10 10204 */