题意是求矩形覆盖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 ; }