알고스팟 - 너드인가, 너드가 아닌가? 2

문제 : 너드인가, 너드가 아닌가? 2 (난이도 : 中)

 

https://algospot.com/judge/problem/read/NERD2

 

 분석

 너드인가를 판단하는 매게 변수가 두 가지로 주어졌다. 너드가 아닌 경우는 두 가지 매게 변수 모두 다른 포인트보다 작을 경우이다. 이런 유형을 다룰 땐 주어진 데이터를 좌표평면 위에 그리면 쉽게 해결할 수 있다.

 

좌표 평면

 이렇게 좌표 평면위에 두면 할 일이 간단해진다. 지배하는 점들의 규칙을 살펴보면 x좌표가 커질수록 y좌표가 작아짐을 알 수 있다. 따라서 새로운 데이터를 추가할 때 기존 지배하는 점의 가장 오른쪽 x좌표보다 큰 지, 아니라면 y 값이 큰 지를 판단하면 된다.

 

 STL의 map을 이용하기 좋은 문제 상황이다. 

 

 구현

map<int, int> coords;
// 새로운 점 (x, y)가 기존의 다른 점들에 지배당하는지 확인
bool isDominated(int x, int y)
{
	// x보다 오른쪽에 있는 점 중 가장 왼쪽의 있는 점을 찾는다.
	map<int, int>::iterator it = coords.lower_bound(x);
	// 없다면 지배 당하지 않는 점.
	if (it == coords.end()) return false;

	// x보다 오른쪽에 있는 점 중 가장 위에 있는 점이다.
	// (x, y)가 어느 점에 지배되려면 이 점에도 지배되어야함
	return y < it->second;
}

// 새로운 점 (x, y)에 지배당하는 점들을 트리에서 제거
void removeDominated(int x, int y)
{
	map<int, int>::iterator it = coords.lower_bound(x);
	// (x, y) 보다 왼쪽에 있는 점이 없는 경우
	if (it == coords.begin()) return;

	--it;
	while (true)
	{
		// (x, y) 바로 왼쪽에 오는 점을 찾는다.
		// it 포인트가 (x, y) 점에 지배되지 않는다면 종료
		if (it->second > y) break;
		// 이전 점이 더 없으므로 it만 지우고 종료
		if (it == coords.begin())
		{
			coords.erase(it);
			break;
		}

		// 이전 점으로 iterator를 옮기고 it를 지운다.
		else
		{
			map<int, int>::iterator jt = it;
			--jt;
			coords.erase(it);
			it = jt;
		}
	}
}

// 새 점 (x, y)가 추가되었을 때 coords를 갱신하고,
// 다른 점에 지배당하지 않는 점들의 개수를 반환한다.
int registered(int x, int y)
{
	// (x, y)가 지배당하는 경우 버린다.
	if (isDominated(x, y)) return coords.size();
	// 기존에 있던 점 중 (x, y)에 지배당하는 점들을 지운다.
	removeDominated(x, y);
	coords[x] = y;
	return coords.size();
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		int n;
		cin >> n;
		int ans = 0;
		for (size_t i = 0; i < n; i++)
		{
			int x, y;
			cin >> x >> y;
			ans += registered(x, y);
		}
		cout << ans << '\n';
	}
	return 0;
}