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

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();
}