hdu 3265 线段树扫描线（拆分矩形）

题意：

给你n个矩形，每个矩形上都有一个矩形的空洞，所有的矩形都是平行于x,y轴的，最后问所有矩形的覆盖面积是多少。

思路：

是典型的矩形覆盖问题，只不过每个矩形上多了一个矩形洞，我的做法是吧当前的矩形分成四个小的矩形，然后用线段树的扫描线扫一遍就ok了，记得要用INT64 ,自己没注意这个问题wa了一次。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N 300000

#define lson l ,mid ,t << 1

#define rson mid ,r ,t << 1 | 1



using namespace std;

typedef struct

{

   __int64 l ,r ,h ,mk;

}EDGE;

__int64 len[N] ,cnt[N];

EDGE edge[N*2];

bool camp(EDGE a ,EDGE b)

{

   return a.h < b.h || a.h == b.h && a.mk > b.mk;

}

void Pushup(__int64 l ,__int64 r ,__int64 t)

{

   if(cnt[t]) len[t] = r - l;

   else if(l + 1 == r) len[t] = 0;

   else len[t] = len[t<<1] + len[t<<1|1];

}

void Update(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b ,__int64 c)

{

   //printf("%d %d %d\n" ,l ,r ,t);

   if(l == a && r == b)

   {

      cnt[t] += c;

      Pushup(l ,r ,t);

      return;

   }

   __int64 mid = (l + r) >> 1;

   if(b <= mid) Update(lson ,a ,b ,c);

   else if(a >= mid) Update(rson ,a ,b ,c);

   else

   {

      Update(lson ,a ,mid ,c);

      Update(rson ,mid ,b ,c);

   }

   Pushup(l ,r ,t);

}

__int64 abss(__int64 x)

{

   return x < 0 ? -x : x;

}

int main ()

{

   __int64 i ,j ,n ,x1 ,x2 ,x3 ,x4 ,y1 ,y2 ,y3 ,y4 ,id;

   __int64 xx1 ,xx2 ,yy1 ,yy2;

   while(~scanf("%I64d" ,&n) && n)

   {

      for(id = 0 ,i = 1 ;i <= n ;i ++)

      {

         scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d" ,&x1 ,&y1 ,&x2 ,&y2 ,&x3 ,&y3 ,&x4 ,&y4);

         x1 ++ ,y1 ++ ,x2 ++ ,y2 ++ ,x3 ++ ,y3 ++ ,x4 ++ ,y4 ++;

         // x1 y2 x2 y4

         xx1 = x1 ,xx2 = x2 ,yy1 = y2 ,yy2 = y4;

         if(abss(xx1 - xx2) && abss(yy1 - yy2))

         {

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;

         }

          // x1 y3 x2 y1

         xx1 = x1 ,xx2 = x2 ,yy1 = y3 ,yy2 = y1;

         if(abss(xx1 - xx2) && abss(yy1 - yy2))

         {

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;

         }

          // x1 y4 x3 y3

         xx1 = x1 ,xx2 = x3 ,yy1 = y4 ,yy2 = y3;

         if(abss(xx1 - xx2) && abss(yy1 - yy2))

         {

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;

         }

          // x4 y4 x2 y3

         xx1 = x4 ,xx2 = x2 ,yy1 = y4 ,yy2 = y3;

         if(abss(xx1 - xx2) && abss(yy1 - yy2))

         {

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;

            edge[++id].l = xx1;

            edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;

         }

      }

      sort(edge + 1 ,edge + id + 1 ,camp);

      __int64 Ans = 0;

      memset(len ,0 ,sizeof(len));

      memset(cnt ,0 ,sizeof(cnt));

      edge[0].h = edge[1].h;

      for(i = 1 ;i <= id ;i ++)

      {

         Ans += len[1] * (edge[i].h - edge[i-1].h);

         Update(1 ,50001,1 ,edge[i].l ,edge[i].r ,edge[i].mk);

      }

      printf("%I64d\n" ,Ans);

   }

   return 0;

}

巴特西

hdu 3265 线段树扫描线（拆分矩形）

最新文章

热门文章