Submission #1136127

#TimeUsernameProblemLanguageResultExecution timeMemory
1136127fzyzzz_zAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
109 ms8568 KiB
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 

    int n; 
    cin >> n; 
    vector<pair<int, int>> a(n); 
    for (auto & [x, y]: a) {
        cin >> x >> y; 

        auto x1 = x - y; 
        auto y1 = x + y; 

        x = x1; 
        y = y1; 
    }

    sort(a.begin(), a.end()); 

    // find upper hull 
    vector<pair<int, int>> b; 
    for (auto [x, y]: a) {
        if (b.size() && b.back().first == x && b.back().second <= y) b.pop_back(); 
        if (!b.size() || y > b.back().second) b.push_back({x, y}); 
    }

    cout << b.size() << '\n'; 


    return 0; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...