BOJ 17026 - Mountain view (라인스위핑)

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

 

<문제설명>

전체선분의 개수에서 어떤 선분에 완전히 포함되는 선분의 개수를 뺀 나머지를 구해라.

(입력 x,y면 선분은 [x-y, x+y])

 

<풀이>

선분 [l,r] n개에 대해 l기준으로 오름차순 정렬하되 l이 같다면 r기준 내림차순 정렬한다.

 

선분들을 차례로 돌면서 r의 최대값을 mx에 유지하고 mx보다 크다면 ans++해준다.

 

어떤 선분에 포함되는 선분의 개수를 구하고싶다면?  n-ans

 

<코드>

int n;
P p[MAX];
int main() {
	FAST;
	cin >> n;
	for (int i = 0,x,y; i < n; i++) {
		cin >> x >> y;
		p[i].first = x - y, p[i].second = x + y;
	}
	sort(p, p + n, [](P p1, P p2) {
		if (p1.first == p2.first)
			return p1.second > p2.second;
		return p1.first < p2.first;
		});

	int mx = -2e9, ans=0;
	for (int i = 0; i < n; i++) {
		if (p[i].second > mx) {
			mx = p[i].second;
			ans++;
		}
	}

	cout << ans;
}