usaco
USACO SILVER::2019 January - Mountain View
USACO SILVER
USACO SILVER::2019 January - Mountain View
Mountain View
- level : Gold 4
- tag : constructive algorithm, sorting, stack
- 풀이 방법이 매우 신기합니다.
- 꼭 익혀두어야겠습니다.
Point
- n이 주어집니다.
- 2차원 평면상의 정점 n개가 주어집니다.
- 주어진 정점은 한 변이 x축에 놓여있고, 해당 정점의 각이 90도인 직각삼각형을 표현합니다.
- 이때, 다른 삼각형에 의해서 가려지지 않는 삼각형의 갯수를 출력합니다.
Design(x)
- 직각 삼각형의 양 쪽 변을 이용하여 관계식을 이끌어내는데는 성공하였지만, 결정적으로 counting을 하지 못하였습니다.
- 아래 풀이는 대회의 솔루션을 참고하였고, 카운팅하는 부분에서 배울점이 많습니다.
- 주어진 정점 x, y를 이용하여 삼각형을 그려보면,
- x축과 닿아있는 두 정점은 x-y와 x+y인 것을 알 수 있습니다.
- 그럼 이제 이를 이용하여 어떤게 가려져있는 삼각형인지 파악할 수 있습니다.
- 먼저 x-y값 기준으로 전체 삼각형을 오름차순 정렬합니다.
- x-y의 값이 같은 경우, x+y값을 기준으로 내림차순 정렬합니다.
- 이 정렬된 삼각형을 순서대로 훑는 것은, 좌표평면에서 가장 좌측에 있는 삼각형부터 훑고 지나가는 것과 같습니다.
- 훑는 것 기준이 x-y이므로, 현재 정점까지 오면서 가장 큰 x+y의 값을 mx라 칭하고,
- 이 값이 갱신될때마다 정답을 카운트해주는 로직입니다.
- 즉, 좌측 삼각형부터 훑어가다가
- mx값이 갱신되는 경우는, 이전 삼각형들에 의해 가려지지 않는 경우이고
- mx값이 갱신되지 않는 경우는, 이전 삼각형들에 의해 가려지는 경우입니다.
Big O(time)
- O(NlogN)
Big O(memory)
Code(x)
// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 100000 + 10;
#define MOD 1000000007
using namespace std;
int n;
int cid[MAXN];
int x[MAXN], y[MAXN];
int pos[MAXN], neg[MAXN];
bool cmp(int i, int j){
if(neg[i] == neg[j]) return pos[i] > pos[j];
else return neg[i] < neg[j];
}
void process(){
cin >> n;
rep(i, 0, n){
cin >> x[i] >> y[i];
pos[i] = x[i] + y[i], neg[i] = x[i] - y[i];
cid[i] = i;
}
sort(cid, cid + n, cmp);
int ans = 0;
int mx = -1;
rep(i, 0, n){
if(pos[cid[i]] > mx){
mx = pos[cid[i]];
ans++;
}
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}