https://www.acmicpc.net/problem/10672
문제 요약
2차원 공간에서 길이가 1인 소들이 경주를 한다. 소들의 첫 위치와 속도가 주어진다. 소는 x축 +방향으로 이동하고 다른 소에게 가려질 수 있다. (0,0)에서 y축 +방향을 바라 볼때 볼 수 있는 소의 개수를 구해라.
풀이 (NlogN)
- 스위핑
- 트리 셋
소가 0을 지나는 시간의 시작점과 끝점을 스위핑한다. 각 점에서 0을 지나고 있는 소중 y값이 가장 작은 소를 볼 수 있다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;cin>>n;
vector<array<int,2>> a;
for(int i=0,x,y,r;i<n;i++)
cin>>x>>y>>r,x=-x,a.push_back({r*(x-1),y}),a.push_back({r*x,-y});
sort(a.begin(),a.end());
set<int> ls,is;
for(int i=0;i<a.size();) {
int j;
for(j=i;j<a.size()&&a[j][0]==a[i][0];j++) {
if(a[j][1]>0)
ls.insert(a[j][1]);
else
ls.erase(-a[j][1]);
}
if(ls.size())
is.insert(*ls.begin());
i=j;
}
cout<< is.size();
}
'풀이' 카테고리의 다른 글
[백준] 16763 - Fine Dining (c++) (0) | 2025.01.22 |
---|---|
[백준] 9569 - No Change (c++) (0) | 2025.01.20 |
[백준] 11211 - Count von Walken’s Fence (c++) (0) | 2025.01.16 |
[백준] 19671 - Lasers (c++) (0) | 2025.01.16 |
[백준] 26972 - Barn Tree (c++) (0) | 2025.01.16 |