Atlantis [line segment tree + scanline + discretization]

POJ1151,ACwing247

Title:

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

Some of them even include partial maps of the island.

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 the total area.

Input format:

The input contains multiple sets of test cases.

For each set of test cases, the first line contains the integer nn, representing the total number of maps.

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 and lower right corner of the map respectively.

Notice that the x axis extends from top to bottom and the y axis extends from left to right.

Pay attention to the tips here, that is, the lower left corner and upper right corner we normally understand

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

Output format:

Output two lines for each set of test cases.

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

The second line outputs Total explored area: a, where a is the total map area (that is, the area of all rectangles in this test case. Note that if an area is included by multiple maps, it is only calculated once when calculating the total area), accurate to two digits after the decimal point.

Output a blank line after each test case.

Data range:

1≤n≤10000,
0≤x1<x2≤100000,
0≤y1<y2≤100000
Note that the upper limit of the scope of this question n is strengthened to 10000.

Sample input:

2
10 10 20 20
15 15 25 25.5
0

Sample output:

Test case #1
Total explored area: 180.00 

Idea:

If the array after y-axis discretization is ys[5.1,6.2,8.5,10.8]

We assume that the parent nodes of nodes [1,1] and [2,2] in the line segment tree are [1,2]. To [1,2] the len of this node can map 8.5 and 6 in the discretization interval

2. However, if the root node is [0,2], to query the length len of [1,2], we will divide [0,2] into [0,1] and [2,2], which will cut off the required interval.

Therefore, another mapping method is adopted. Map the interval [0,0] to 5.16.5 and [1,1] to 6.28.5. Then the minimum unit of the segment tree is a length rather than a point, that is, the length of [l,r] = ys[r+1]-ys[l].

After discretization, the Y-axis of each node of the line segment tree does not cross, and then the width of the y-axis is accumulated multiplied by the distance swept by x, and then the product is accumulated, which is the final area.

code:

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e4+5;

int n;
//--------------------------------------
struct Node{
    int l,r;        //Storage interval
    int count;      //The number of times the current section has been effectively overwritten
    double len;     //Effective length in the current section
} tree[N << 3];    //Store segment tree
//--------------------------------------
struct edge{
    double x,y1,y2; //Three coordinates
    int k;          //1 indicates the line on the left of the rectangle, - 1 indicates the line on the right of the rectangle
} E[N << 1];        //Storage edge
int k;              //How many edges are stored
//--------------------------------------
vector<double> v;   //For discretization

bool cmp(edge a,edge b){
    return a.x < b.x;
}

void pushup(int p){
    //If a whole segment [l,r] of the node needs to be calculated, directly look up the discretized table v
    if(tree[p].count)
        tree[p].len = v[tree[p].r + 1] - v[tree[p].l];
    //If there is no full coverage, the effective length of the left and right children is added
    else if(tree[p].count == 0 && tree[p].l != tree[p].r)
        tree[p].len = tree[p<<1].len + tree[p<<1|1].len;
    //The smallest clip is not selected
    else
        tree[p].len = 0;
}

void build(int p,int l,int r){
    tree[p] = {l,r,0,0};
    if(l == r)
        return;
    int lc = p<<1,rc = p<<1|1,mid = l+r>>1;
    build(lc,l,mid);
    build(rc,mid + 1,r);
    pushup(p);
}

void update(int p,int l,int r,int k){
    //If you encounter this edge for the first time, count+1 is valid. If you encounter it for the second time, then long-1 is invalid
    if(tree[p].l == l && tree[p].r == r)
        tree[p].count += k;
    else{
        int lc = p<<1,rc = p<<1|1,mid = tree[p].l+tree[p].r>>1;
        if(r<=mid)
            update(lc,l,r,k);
        else if(l > mid)
            update(rc,l,r,k);
        else
            update(lc,l,mid,k),update(rc,mid + 1,r,k);
    }
    pushup(p);
}

int find_w(double x){
    return lower_bound(v.begin(),v.end(),x) - v.begin();
}

signed main(){
    int T = 0;
    while(cin>>n && n){
        k = 0;
        v.clear();
        cout<<"Test case #"<<++T<<"\n";
        double x1,y1,x2,y2;
        double ans = 0;
        for(int i = 1;i <= n;++i){
            cin>>x1>>y1>>x2>>y2;
            E[k].x = x1;E[k].y1 = y1,E[k].y2 = y2,E[k++].k = 1;
            E[k].x = x2;E[k].y1 = y1,E[k].y2 = y2,E[k++].k = -1;
            v.push_back(y1),v.push_back(y2);        //Store the two sides of a rectangle and prepare for discretization
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end()); //De duplication discretization

        build(1,0,v.size() - 2);            //Establish segment tree

        sort(E,E + k,cmp);                      //Sort all lines by x from left to right for subsequent scanning

        for(int i = 0;i < k;++i){
            if(i > 0)
                ans += tree[1].len * (E[i].x - E[i-1].x);
            update(1,find_w(E[i].y1),find_w(E[i].y2) - 1,E[i].k);
        }
//        cout<<"Total explored area: "<<ans<<"\n\n";
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}