博客

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

现在有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;
}