Proficient.
Put your skills to the test.

Problem summary

A width-N, height-M rectangle is cut repeatedly. A query (x,y), still inside the remaining paper, removes everything above the upward45° and135° rays from that point. After each cut, print the remaining area to two decimal places. Every query removes positive area.

Source clarification. The ordered-envelope approach follows the official full-score editorial. Coordinates are left unscaled; exact quarter-area units replace floating-point integration. Editorial: https://infos.infosbg.com/files/Contests/ETI/2021/B/analyses/B22_Cutting_analysis.docx

Constraints

1≤N·M≤10^12; 1≤Q≤150000;0≤x≤N,0≤y≤M; each point is inside the current paper.

Worked example

Original statement sample.

20 10
4
10 5
4 7
0 1
16 3

175.00
167.00
138.50
103.00

Solution analysis

1. The remaining upper boundary is the lower envelope of the original horizontal ceiling M and cones y+|X−x| from previous cuts. Keep only cone apexes that still appear on that boundary, ordered by x in a map. A new lower apex can make some neighboring old apexes irrelevant.
2. Scan left and right from the new point. Delete an old apex (u,v) whenever y+|u−x|≤v: the new cone is nowhere higher than that old cone. Once a neighbor is not dominated, farther apexes in that direction are also safe. Every inserted apex can be removed only once.
3. Only intervals next to inserted or deleted apexes change area. Between adjacent apexes, the upper boundary is the minimum of a rising line, a falling line, and M; integrate these trapezoids/triangles exactly. Store four times the area, so half-coordinate intersections need no floating point. In the sample the first cut removes a triangle of area25, leaving175; later cuts give167,138.50 and103.

Why it works

For adjacent surviving apexes, all other cones are higher on the interval between them, so their two branches and the ceiling determine its whole boundary. A dominated apex can never become relevant again because future operations only lower the envelope. Replacing local interval contributions therefore preserves the exact integral, and the final integral is precisely the remaining paper area.

Watch out. Recomputing all boundary intervals after every cut becomes quadratic. Include the two paper boundaries and the ceiling M. Intersections can have half-integer coordinates, so integer areas alone are insufficient. The implementation uses exact quarter-area units and prints .00,.25,.50 or.75.

An independently written complete program with standard headers.

// Key idea: For adjacent surviving apexes, all other cones are higher on the interval between them, so
// their two branches and the ceiling determine its whole boundary. A dominated apex can never become
// relevant again because future operations only lower the envelope.
#include<iomanip>
#include<iostream>
#include<map>
using namespace std;
class Paper{
    long long width;
    long long height;
    long long area4;
    map<long long,long long>apex;
    using Iterator=map<long long,long long>::iterator;
    long long oneSide(long long length,long long level)const{
        long long rise=height-level;
        if(length<=rise){
            return 4*level*length+2*length*length;
        }
        return 4*height*length-2*rise*rise;
    }
    long long contribution(Iterator left,Iterator right)const{
        if(left==apex.begin()&&next(right)==apex.end()){
            return 4*width*height;
        }
        if(left==apex.begin()){
            return oneSide(right->first,right->second);
        }
        if(next(right)==apex.end()){
            return oneSide(width-left->first,left->second);
        }
        long long length=right->first-left->first;
        long long a=left->second;
        long long b=right->second;
        long long missingA=height-a;
        long long missingB=height-b;
        if(missingA+missingB<length){
            return 4*height*length-2*(missingA*missingA+missingB*missingB);
        }
        long long difference=a-b;
        return 2*(a+b)*length+length*length-difference*difference;
    }
    void erase(Iterator point){
        auto left=prev(point);
        auto right=next(point);
        area4-=contribution(left,point)+contribution(point,right);
        area4+=contribution(left,right);
        apex.erase(point);
    }
    public:
    Paper(long long n,long long m):width(n),height(m),area4(4*n*m){
        apex[-1]=0;
        apex[width+1]=0;
    }
    void cut(long long x,long long y){
        auto same=apex.find(x);
        if(same!=apex.end()){
            erase(same);
        }
        auto right=apex.lower_bound(x);
        while(prev(right)!=apex.begin()){
            auto point=prev(right);
            if(y+x-point->first>point->second){
                break;
            }
            erase(point);
        }
        while(next(right)!=apex.end()&&y+right->first-x<=right->second){
            auto obsolete=right++;
            erase(obsolete);
        }
        auto left=prev(right);
        area4-=contribution(left,right);
        auto current=apex.emplace(x,y).first;
        area4+=contribution(left,current)+contribution(current,right);
        cout<<area4/4<<'.'<<setw(2)<<setfill('0')<<(area4%4)*25<<'\n';
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,m;
    int q;
    cin>>n>>m>>q;
    Paper paper(n,m);
    while(q--){
        long long x,y;
        cin>>x>>y;
        paper.cut(x,y);
    }
}