Topic address: https://www.acwing.com/problem/content/249/

Topic description:

Several ancient Greek books contain descriptions of the fabled island of Atlantis.

Some of them even include maps of parts of the island.

But unfortunately, these maps describe different areas of Atlantis.

Your friend Bill must know the total area of ​​the map.

You volunteered to write a program to calculate this total area.

input format

The input contains sets of test cases.

For each set of test cases, the first line contains the integer n, which represents the total number of maps.

The next n lines depict each map, each line contains four numbers x1,y1,x2,y2 (not necessarily integers), (x1,y1) and (x2,y2) are the upper left corner of the map and lower right corner position.

Note that the x-axis runs from top to bottom, and the y-axis runs from left to right.

When the input use case n=0, it means that the input is terminated, and the use case does not need to be processed.

output format

Each set of test cases outputs two lines.

The first line outputs "Test case #k", where k is the number of the test case, starting with 1.

The second line outputs "Total explored area: a", where a is the total map area (that is, the sum of all rectangles in this test case, note that if an area is contained by multiple maps, it will only be calculated once when calculating the total area) , accurate to two decimal places.

Output a blank line after each test case.

data range

1≤n≤10000
0≤x1<x2≤100000
0≤y1<y2≤100000

Solution: This is a scan line + line segment tree problem.

We can transform the rectangle into the operation of +1 on the left and -1 on the right. Each time, we only need to look at the length of the current interval greater than 0 and multiply it by the width to get the area of ​​the current part, and add up all the areas.

However, because the ordinate may not be an integer, it is not possible if it is a direct line segment tree. First, it needs to be discretized to discretize all the ordinates. This can be done without pushdown(), first of all, pushdown() is used in query() and modify(), and the direct tr[u].len we want to query is enough. As for modify(), since +1 and minus 1 come in pairs, it doesn't have to be passed down.

AC code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct segment{
    double x,y1,y2;//Stores an ordinate interval 
    int k;
}seg[N*2];
struct node {
    int l,r;
    int cnt;//Indicates how many times the current interval has been covered, but it is not passed to the child nodes, 
    double len;//Indicates the length of the current interval greater than 0 
}tr[8*N];
vector<double>all;//For discretization of interval abscissa 

int cmp(struct segment a1,struct segment a2){
    return a1.x<a2.x;
}

int find(double y){//return all The first is greater than or equal to y Add 1 to the subscript, because the original subscript starts from 0, and we need to start from 1 
    return lower_bound(all.begin(),all.end(),y)-all.begin()+1;
}

void pushup(int u){//Updating 
    if(tr[u].cnt) tr[u].len=all[tr[u].r]-all[tr[u].l-1];
    else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    else tr[u].len=0;
}

void build(int u,int l,int r){//Build a segment tree 
    tr[u].l=l;
    tr[u].r=r;
    tr[u].cnt=0;
    tr[u].len=0;
    if(l==r){
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    return ;
}

void modify(int u,int l,int r,int d){//Interval modification, what needs to be noted here is the modification[l,r]actually represents all[l-1],all[r]interval modification 
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].cnt+=d;
        pushup(u); 
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,d);
    if(r>mid) modify(u<<1|1,l,r,d);
    pushup(u);
    return ;
}

int main(){
    int n,T=0;
    while(~scanf("%d",&n)){
        if(!n) return 0;
        all.clear();
        for(int i=1,j=1;i<=n;i++){
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            seg[j++]={x1,y1,y2,1};
            seg[j++]={x2,y1,y2,-1};
            all.push_back(y1),all.push_back(y2);
        }
        sort(seg+1,seg+2*n+1,cmp);
        sort(all.begin(),all.end());
        all.erase(unique(all.begin(),all.end()),all.end());
        build(1,1,all.size()-1);
        double ans=0;
        for(int i=1;i<=n*2;i++){
            if(i>1) ans+=(double)tr[1].len*(seg[i].x-seg[i-1].x);
            modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
        }
        cout<<"Test case #"<<++T<<endl;
        printf("Total explored area: %.2lf\n\n",ans); 
    }
    return 0;
}

Written at: 202/8/29 12:34