본문 바로가기
풀이

[백준] 10672 - Stampede (c++)

by 땅왕 2025. 1. 16.

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