[BOJ] 17026 Mountain View

문제

17026번: Mountain View

From her pasture on the farm, Bessie the cow has a wonderful view of a mountain range on the horizon. There are $N$ mountains in the range ($1 \leq N \leq 10^5$). If we think of Bessie's field of vision as the $xy$ plane, then each mountain is a triangle whose base rests on the $x$ axis. The two sides of the mountain are both at 45 degrees to the base, so the peak of the mountain forms a right angle. Mountain $i$ is therefore precisely described by the location $(x_i, y_i)$ of its peak. No two mountains have exactly the same peak location.

https://www.acmicpc.net/problem/17026

풀이

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
 
int n, ans = 1, tmp;
vector<pii> v;
 
bool comp(pii a, pii b) {
    if (a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}
 
int main() {
    scanf("%d", &n);
    for(int a, b, i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        v.push_back({a - b, a + b});
    }
    sort(v.begin(), v.end(), comp);
    tmp = v[0].second;
    for(int i = 1; i < n; i++) {
        if (v[i].second > tmp) {
            tmp = v[i].second;
            ans++;
        }
    }
    printf("%d", ans);
}