USACO 2019 January Contest Silver Division - Mountain View

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We transform the points in intervals which are sorted by the left end. For each interval in the sorted order, we check if a mountain is new by seeing if the ending is past the max end.

Source code

The source code in C++ can be seen below.

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

pair<int, int> pct[100002];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.first == b.first)
        return a.second > b.second;
    return a.first < b.first;
}
int main()
{
    ifstream cin("mountains.in");
    ofstream cout("mountains.out");

    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int a, b;
        cin >> a >> b;
        pct[i] = {a-b, a+b};
    }
    sort(pct+1, pct+n+1, cmp);
    int ans = 0;
    int mx = -(1<<30);
    for(int i = 1; i <= n; ++i)
    {
        if(pct[i].second > mx)
        {
            ++ans;
            mx = pct[i].second;
        }
    }
    cout << ans;
    return 0;
}