欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU3265 扫描线+线段树 区间并

程序员文章站 2022-07-13 11:03:01
...

传送门:HDU3265

题意:N个海报,每个海报中间有个矩形的洞。问这N个海报覆盖面积和是多少。


分析: 非常经典的题目了,扫描线+线段树 进行 区间并操作 

既然海报内有块矩形不能计算入内,只要把海报分为四块不重叠的部分就好了。

重点是空间限制比较紧,交了若干次才A的。。改用unsigned short(0...65536) 存储坐标才A了。。

注意:若扫描线个数小于2直接输出0,如果按常规的线段树求区间和会返回RE。。


截图纪念一下这个让我调试了N久bug的题目。。

HDU3265 扫描线+线段树 区间并


代码如下:

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 4e5+10;
struct Line{
   unsigned short x,y1,y2;
   bool f;
   bool operator <(const Line &rhs) const {
      return x<rhs.x;
   }
}line[maxn];
int y[maxn];
int n,tot;

inline void addLine(int a, int b,int c, int d) {
   tot++;
   line[tot].x = a; line[tot].y1 = b; line[tot].y2 = d;
   line[tot].f = 1; y[tot] = b;
   tot++;
   line[tot].x = c; line[tot].y1 = b; line[tot].y2 = d;
   line[tot].f = 0; y[tot] = d;
}

struct node{
    int l,r;
    int c,len;
    int lf,rf;
};

struct Tree{
     node tr[maxn*4];
     #define lch(u) (u<<1)
     #define rch(u) (u<<1|1)
     #define Mid (tr[u].l+tr[u].r)>>1

     void build(int u, int a, int b) {
         tr[u].l = a; tr[u].r = b;
         tr[u].lf = y[a]; tr[u].rf = y[b];
         tr[u].c = tr[u].len = 0;
         if (a+1 == b) return ;
         build(lch(u),a,Mid);
         build(rch(u),Mid,b);
     }

    inline void cal(int u){
         if (tr[u].c > 0) {
             tr[u].len = tr[u].rf - tr[u].lf;
         }
         else {
            if (tr[u].l+1 == tr[u].r) tr[u].len = 0;
            else tr[u].len = tr[lch(u)].len + tr[rch(u)].len;
         }
     }

     void update(int u, Line e){
         if (e.y1 == tr[u].lf && e.y2 == tr[u].rf) {
            if (e.f == 1) tr[u].c++; else tr[u].c--;
            cal(u);
            return ;
         }
         if (e.y2 <= tr[lch(u)].rf) update(lch(u),e);
         else if (e.y1 >= tr[rch(u)].lf) update(rch(u),e);
         else {
            Line tmp = e;
            tmp.y2 = tr[lch(u)].rf;
            update(lch(u),tmp);

            tmp = e;
            tmp.y1 = tr[rch(u)].lf;
            update(rch(u),tmp);
         }
         cal(u);
     }
}T;

int x[10];

int main(){
    while (scanf("%d",&n)==1 && n){
        tot = 0;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=8; j++) scanf("%d",&x[j]);
            if (x[1]<x[5] && x[2]<x[4]) addLine(x[1],x[2],x[5],x[4]);
            if (x[7]<x[3] && x[2]<x[4]) addLine(x[7],x[2],x[3],x[4]);
            if (x[5]<x[7] && x[8]<x[4]) addLine(x[5],x[8],x[7],x[4]);
            if (x[5]<x[7] && x[2]<x[6]) addLine(x[5],x[2],x[7],x[6]);
        }
        sort(line+1,line+tot+1);
        sort(y+1,y+tot+1);

        if (tot<2) {
            printf("0\n");
            continue;
        }

        T.build(1,1,tot);
        T.update(1,line[1]);

        unsigned int ans = 0;
        for (int i=2; i<=tot; i++) {
            ans += T.tr[1].len*(line[i].x-line[i-1].x);
            T.update(1,line[i]);
        }
        printf("%u\n",ans);
    }
    return 0;
}