BOJ 18879 - The moo particle (기하, 수학)

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

좌표평면 없이 푸는 머리좋은 사람들도 있을 것 같음

 

 

<문제설명>

n개의 요소가 주어진다. 각각의 요소는 x,y값으로 표현된다. (n<=1e5, |x,y|<=1e9)

 

xi <= xj && yi<= yj 를 만족하는 i,j 요소를 서로 연결됐다고 볼 때, 컴포넌트의 개수를 구해라

 

 

<풀이>

그래프가 완전그래프에 가까울정도로 빽빽해질 여지가 있으므로, 직접 간선을 이을 수 있는 상황이 아니다.

 

다음과 같은 입력을 좌표평면에 그려보면 아래와 같다.

7

1 0

0 1

-1 0

0 -1

3 -5

4 -4

2 -2

http://www.usaco.org/current/data/sol_moop_silver_open20.html

 

A : min(y1,y2,…,yi)>max(yi+1,yi+2,…,yN) 

B : max(x1,x2,…,xi)<min(xi+1,xi+2,…,xN)

 

A와 B를 동시에 만족하면 i번째 정점은 기존 컴포넌트에 포함된다.

 

<코드>

const int MAX = 1e5 + 4;
const int INF = 1e9 + 1;

int n;
int x[MAX], y[MAX], id[MAX];
int mnx[MAX], mxy[MAX];

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		id[i] = i;
	}
	sort(id, id + n, [](int i1, int i2) {
		if (x[i1] == x[i2]) return y[i1] > y[i2];
		else return x[i1] < x[i2];
		});

	mxy[n-1] = y[id[n - 1]];
	for (int i = n - 2, cy; i >= 0; i--) {
		cy = y[id[i]];
		mxy[i] = max(mxy[i + 1], cy);
	}
	mnx[n - 1] = x[id[n - 1]];
	for (int i = n - 2, cx; i >= 0; i--) {
		cx = x[id[i]];
		mnx[i] = min(mnx[i + 1], cx);
	}
	int cnt = 0;
	int mn = INF, mx = -INF;
	for (int i = 0; i < n; i++) {
		if (mn > mxy[i] && mx < mnx[i]) cnt++;
		mn = min(mn, y[id[i]]);
		mx = max(mx, x[id[i]]);
	}
	cout << cnt << '\n';
}

 

<생각>

x기준 정렬했기 때문에 B는 고려할 필요 없다. 위 코드는 그걸 반영하지 않았다.