题意是求矩形覆盖2次以上的面积
第一道扫面线题 看了网上一些扫描线的讲解 没怎么看懂 自己试着敲了一下 感觉还行 比较容易懂
关于扫描线的概念就不多说了 直接上题
离散化：对x轴
线段树 ：对离散后的x值
扫描线：对与x轴平行的边
注意节点的的子树 应为必须是一个区间 所有最小区间为为1-2 2-3 3-4 4-5 ??????????
#include
#include
#include
#include
using namespace std
; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1)
struct node
{ double y
; int x1
,x2
; int flash
; }A
[3100
]; struct Node
{ double x
; int tt
; int ii
; }scatter
[3100
]; int leap
[10000
];//标记节点 如果==-1说明当前节点表示的区间不是不是一样的值 否则为对应的值 int n
; double map
[3100
];//每个下标对应浮点型x的值 int cmp
(Node a
,Node b
) { return a
.x
<b
.x
; } int cmp2
(Node a
,Node b
) { if(a
.ii
!=b
.ii
) return a
.ii
<b
.ii
; else return a
.x
<b
.x
; } int cmp3
(node a
,node b
) { return a
.y
<b
.y
; } int update
(int L
,int R
,int left
,int right
,int mark
,int k
) { int mid
=(L
+R
)/2
; if(L
==left
&&right
==R
) { if(leap
[mark
]>=0
) { leap
[mark
]+=k
; } else { update
(L
,mid
,L
,mid
,LL
(mark
),k
); update
(mid
,R
,mid
,R
,RR
(mark
),k
); if(leap
[LL
(mark
)]==leap
[RR
(mark
)]) leap
[mark
]=leap
[LL
(mark
)]; } } else { if(leap
[mark
]>=0
) { leap
[LL
(mark
)]=leap
[mark
]; leap
[RR
(mark
)]=leap
[mark
]; } if(right
<=mid
) { update
(L
,mid
,left
,right
,LL
(mark
),k
); } else if(left
>=mid
) { update
(mid
,R
,left
,right
,RR
(mark
),k
); } else { update
(L
,mid
,left
,mid
,LL
(mark
),k
); update
(mid
,R
,mid
,right
,RR
(mark
),k
); } if(leap
[LL
(mark
)]==leap
[RR
(mark
)]) leap
[mark
]=leap
[LL
(mark
)]; else leap
[mark
]=-1
; } return 0
; } double find
(int L
,int R
,int mark
) { double dis
=0
; if(leap
[mark
]>=2
) { dis
+=map
[R
]-map
[L
]; return dis
; } if(leap
[mark
]>=0
) return 0
; int mid
=(L
+R
)/2
; dis
+=find
(L
,mid
,LL
(mark
))+find
(mid
,R
,RR
(mark
)); return dis
; } int main() { int T
,i
,j
,a
,b
; double x1
,y1
,x2
,y2
; scanf
("%d"
,&T
); while(T
--) { scanf
("%d"
,&n
); memset
(A
,0
,sizeof(A
)); memset
(map
,0
,sizeof(map
)); for(i
=1
;i
<=2
*n
;i
+=2
) { scanf
("%lf%lf%lf%lf"
,&x1
,&y1
,&x2
,&y2
); A
[i
].y
=y1
; A
[i
].flash
=1
; A
[i
+1
].y
=y2
; A
[i
+1
].flash
=-1
; scatter
[i
].x
=x1
; scatter
[i
].ii
=i
; scatter
[i
+1
].x
=x2
; scatter
[i
+1
].ii
=i
; } sort
(scatter
+1
,scatter
+2
*n
+1
,cmp
);//对x来离散 应为x值为浮点型 不能成为数组下标 double k
=-1
; int j
=0
; for(i
=1
;i
<=2
*n
;i
++) { if(scatter
[i
].x
!=k
) { k
=scatter
[i
].x
; scatter
[i
].tt
=++j
; map
[j
]=scatter
[i
].x
; } else scatter
[i
].tt
=j
; } sort
(scatter
+1
,scatter
+2
*n
+1
,cmp2
); for(i
=1
;i
<=2
*n
;i
+=2
) { A
[i
].x1
=scatter
[i
].tt
; A
[i
].x2
=scatter
[i
+1
].tt
; A
[i
+1
].x1
=scatter
[i
].tt
; A
[i
+1
].x2
=scatter
[i
+1
].tt
; } sort
(A
+1
,A
+2
*n
+1
,cmp3
);//把所有与x轴平行的边按对应的y值排序 memset
(leap
,0
,sizeof(leap
)); double area
=0
; a
=A
[1
].x1
; b
=A
[1
].x2
; update
(1
,j
,a
,b
,1
,1
); for(i
=2
;i
<=2
*n
;i
++) { a
=A
[i
].x1
; b
=A
[i
].x2
; area
+=(A
[i
].y
-A
[i
-1
].y
)*find
(1
,j
,1
); if(A
[i
].flash
==1
) update
(1
,j
,A
[i
].x1
,A
[i
].x2
,1
,1
); else update
(1
,j
,A
[i
].x1
,A
[i
].x2
,1
,-1
); } printf
("%.2lf\n"
,area
); } return 0
; }