格子染色(区间合并)

柔光的暖阳◎ 2023-03-04 08:22 3阅读 0赞

在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。

现在有n个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。

问经过n次操作以后，共有多少个格子被染黑，重复染色同一格子只计数一次。

输入格式

第一行包含一个正整数n。

接下来n行，每行包含四个整数x1,y1,x2,y2x1,y1,x2,y2，表示一个操作的两端格子坐标。

若x1=x2x1=x2则是在一列上染色，若y1=y2y1=y2则是在一行上染色。

保证每次操作是在一行或一列上染色。

输出格式

包含一个正整数，表示被染黑的格子的数量。

数据范围

1≤n≤100001≤n≤10000,  
−109≤x1,y1,x2,y2≤109−109≤x1,y1,x2,y2≤109

输入样例：

3
    1 2 3 2
    2 5 2 3
    1 4 3 4

输出样例：

题解:

利用横纵坐标进行区间合并,最后利用暴力法求出交叉点

区间合并时由于要进行排序,所以每条线的横纵坐标顺序会被打乱,所以要把坐标存到一个结构体中去

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <unordered_map>
    using namespace std;
    const int N = 10010;
    
    struct segement{
        int k;
        int l;
        int r;
    };
    
    bool cmp(segement a,segement b){
        return a.l < b.l;
    }
    
    vector<segement> vx[N],vy[N];  //所有横竖坐标的组合
    unordered_map<int,int> mx,my;
    
    int smerge(vector<segement> &segs){
        vector<segement> res;
        sort(segs.begin(),segs.end(),cmp);
        int nodes = 0;
        
        int st = -2e9,ed = -2e9,sk = -2e9;
        for(auto seg : segs){
            if(ed < seg.l){
                if(st != -2e9) {
                    res.push_back({sk,st,ed});
                    nodes += ed - st + 1;
                }
                st = seg.l,ed = seg.r,sk = seg.k;
            }
            else ed = max(ed,seg.r);
        }
        
        if (st != -2e9) {
            nodes += ed - st + 1;
            res.push_back({sk,st,ed});
        }
        
        segs = res;
        return nodes;
    }
    
    int main(){
        int n,x1,y1,x2,y2;
        int xind = 0,yind = 0;
        cin >> n;
        while(n--){
            cin >> x1 >> y1 >> x2 >> y2;
            if(x1 == x2){
                if(mx[x1] == 0) mx[x1] = ++xind;
                int sy1 = min(y1,y2);
                int sy2 = max(y1,y2);
                vx[mx[x1]].push_back({x1,sy1,sy2});
            }
            if(y1 == y2){
                if(my[y1] == 0) my[y1] == ++yind;
                int sx1 = min(x1,x2);
                int sx2 = max(x1,x2);
                vy[my[y1]].push_back({y1,sx1,sx2});
            }
        }
        
        int nodes = 0;
        
        for(int i = 1; i <= xind;++i){
            nodes += smerge(vx[i]);
        }
        for(int i = 1; i <= yind;++i){
            nodes += smerge(vy[i]);
        }
        
        
        cout<<nodes<<endl;
        
        return 0;
    }