Proficient.
Put your skills to the test.

Problem summary

Maintain a set of integer points under insertions and deletions. For a queried existing point, find the largest area of a right triangle with its right angle there and its two legs parallel to the coordinate axes.

Source clarification. The operation prose says the query vertex is stored, but the official example queries (1,2), (3,4), and (4,1) when absent. The solution supports arbitrary query vertices as demonstrated by that example.

Constraints

3 ≤ N ≤ 100,000; 1 ≤ Q ≤ 200,000; −10⁹ ≤ coordinates ≤ 10⁹; no duplicate points; deletions and queried points exist.

Worked example

An independently prepared example for this explanation.

7 10
1 1
1 4
2 3
2 4
3 2
4 4
-3 6
3 1 2
3 3 4
2 1 4
3 3 4
1 7 4
3 3 4
3 1 2
3 4 1
2 1 1
3 1 2

2
2
1
4
1
4.5
0

Solution analysis

1. The horizontal leg must end at a point with the same y, and the vertical leg at a point with the same x. The choices are independent, so maximize each leg length separately.
2. Maintain a map from y to an ordered set of x-coordinates, and a map from x to an ordered set of y-coordinates. The farthest coordinate from a query coordinate is always one of the minimum or maximum elements of its set. Insertions and deletions update both maps.
3. In the official example, querying (4,1) uses the vertical point (4,4) and horizontal point (1,1): the legs have lengths 3 and 3, so the area is 4.5. Query vertices are allowed not to be stored in the official example; using find also supports that case naturally.

Why it works

All legal horizontal endpoints belong to the queried row and all legal vertical endpoints belong to its column. In a sorted set the greatest absolute distance from a fixed coordinate occurs at an extreme. Taking both greatest distances maximizes their nonnegative product, and choosing their endpoints simultaneously yields a valid right triangle whenever both lengths are positive. Both maps exactly reflect every update.

Watch out. The official sample queries points not in the stored set, despite the operation description; support them as well. Use 64-bit products: doubled area can reach 4×10¹⁸. Print halves exactly rather than using floating point.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
// Algorithm: The horizontal leg must end at a point with the same y, and the vertical leg at a
// point with the same x.
using namespace std;
long long farthest(const map<long long,set<long long>>&lines,long long key,long long value){
    auto it=lines.find(key);
    if(it==lines.end()||it->second.empty()){
        return 0;
    }
    return max(llabs(value-*it->second.begin()),llabs(value-*it->second.rbegin()));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    map<long long,set<long long>>rows,columns;
    auto insert=[&](long long x,long long y){
        rows[y].insert(x);
        columns[x].insert(y);
    };
    while(n--){
        long long x,y;
        cin>>x>>y;
        insert(x,y);
    }
    while(q--){
        int type;
        long long x,y;
        cin>>type>>x>>y;
        if(type==1){
            insert(x,y);
        }
        else if(type==2){
            rows[y].erase(x);
            columns[x].erase(y);
        }
        else{
            long long doubled=farthest(rows,y,x)*farthest(columns,x,y);
            cout<<doubled/2;
            if(doubled%2){
                cout<<".5";
            }
            cout<<'\n';
        }
    }
}