POJ 1177 Picture（线段树：扫描线求轮廓周长）-白红宇

POJ 1177 Picture（线段树：扫描线求轮廓周长）

阅读量：793 次

发布时间：2023-03-03

本文共 2470 字，大约阅读时间需要 8 分钟。

题目链接：

题目大意： 给定若干个矩形，求这些矩形重叠形成的图形的轮廓周长。

解题思路：

沿X轴离散化建树：

将X轴的连续值离散化，使其成为离散的点，便于使用线段树进行处理。例如，将矩形的X轴范围从1到100离散化为整数点。

按Y值从小到大排序处理矩形边：

将所有矩形的上下边分别按Y值排序。处理每个矩形时，先处理下边，插入线段树记录其存在，处理上边则删除对应的线段。

线段树状态更新：

线段树记录X轴上的线段状态。当插入下边时，增加线段树中的线段总长度；当删除上边时，减少线段树中的线段总长度。

计算周长变化：

每次处理一个矩形时，计算线段树当前总长度与上一次总长度的差值，即为这次处理带来的周长变化。累加所有变化即为总周长。

左右扫描处理：

分别从X轴的左右两侧扫描，确保所有边界的变化都被正确记录和计算。

代码解析：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               #define LC(a) (a << 1) #define RC(a) (a << 1 | 1) #define MID(a, b) ((a + b) >> 1) using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const int N = 1e4 + 5; struct Node { int l, r, cnt, sum; // sum为测度 } tree[N * 2 * 4]; struct node { int l, r, h, flag; node() {} node(double a, double b, double c, double d) { l = a; r = b; h = c; flag = d; } }; bool cmp(node a, node b) { return a.h < b.h; } void pushup(int p) { if (tree[p].cnt > 0) { tree[p].sum = tree[p].r - tree[p].l + 1; } else if (tree[p].l == tree[p].r) { tree[p].sum = 0; } else { tree[p].sum = tree[LC(p)].sum + tree[RC(p)].sum; } } void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; if (l == r) { tree[p].cnt = tree[p].sum = 0; return; } build(LC(p), l, MID(l, r)); build(RC(p), MID(l, r) + 1, r); pushup(p); } void update(int p, int l, int r, int cnt) { if (l > tree[p].r || r < tree[p].l) { return; } if (l <= tree[p].l && tree[p].r <= r && tree[p].cnt != -1) { tree[p].cnt += cnt; pushup(p); return; } update(LC(p), l, r, cnt); update(RC(p), l, r, cnt); pushup(p); } int main() { int n; while (~scanf("%d", &n)) { int m1 = 0, m2 = 1; for (int i = 1; i <= n; ++i) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1 += N, x2 += N, y1 += N, y2 += N; a[++m1] = node(x1, x2, y1, 1); b[m1] = node(y1, y2, x1, 1); a[++m1] = node(x1, x2, y2, -1); b[m1] = node(y1, y2, x2, -1); } sort(a + 1, a + 1 + m1, cmp); sort(b + 1, b + 1 + m1, cmp); build(1, 1, 2 * N - 1); int ans = 0; for (int i = 1; i <= m1; ++i) { int last = tree[1].sum; int l = a[i].l; int r = a[i].r - 1; update(1, l, r, a[i].flag); ans += abs(tree[1].sum - last); } build(1, 1, 2 * N - 1); for (int i = 1; i <= m1; ++i) { int last = tree[1].sum; int l = b[i].l; int r = b[i].r - 1; update(1, l, r, b[i].flag); ans += abs(tree[1].sum - last); } printf("%d\n", ans); } return 0; }

总结：

通过线段树动态管理X轴上的线段，分别处理矩形的上下边，计算每次更新带来的周长变化，累加得到总周长。这种方法高效且准确，能够处理较大的输入规模。

转载地址：http://gkxfk.baihongyu.com/

你可能感兴趣的文章