입체 공간의 지배 관계
다이아몬드 IV의견: 0
3차원 공간에 \(N\)개의 점이 있다. \(i\)번 점의 좌표는 \((x_i, y_i, z_i)\)이다.
점 \(p\)가 점 \(q\)를 지배한다는 것은 \(x_q \le x_p\), \(y_q \le y_p\), \(z_q \le z_p\)가 모두 성립함을 뜻한다(좌표가 같아도 된다).
각 점 \(i\)에 대해, 자기 자신을 제외하고 점 \(i\)가 지배하는 점의 개수를 \(f(i)\)라 하자. \(d = 0, 1, \dots, N-1\) 각각에 대해 \(f(i) = d\)인 점 \(i\)의 개수를 구하여라. (좌표가 완전히 동일한 두 점은 서로를 지배하므로 서로의 개수에 포함된다.)
\(O(N^2)\) 비교는 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(0 \le x_i, y_i, z_i \le 10^9\)
첫 줄에 점의 개수 \(N\)이 주어진다.
이어서 \(N\)개의 줄에 각 점의 좌표 \(x_i\), \(y_i\), \(z_i\)가 주어진다.
\(N\)개의 줄을 출력한다. \(d\)번째 줄(\(d = 0, 1, \dots, N-1\))에는 정확히 \(d\)개의 점을 지배하는 점의 개수를 출력한다.
4
1 1 1
2 2 2
3 3 3
1 3 2
1
2
0
1점1(1,1,1)은 누구도 지배 못함 -> f=0. 점2(2,2,2)는 점1 지배 -> f=1. 점3(3,3,3)은 모두 지배 -> f=3. 점4(1,3,2)는 점1 지배 -> f=1. f값 분포: 0이 1개, 1이 2개, 2가 0개, 3이 1개.
3
5 5 5
5 5 5
5 5 5
0
0
3좌표가 모두 같으므로 각 점은 나머지 두 점을 지배한다. 모든 점의 f=2. 분포: 0이 0개,1이 0개,2가 3개.
riseoj 작성
출처 Original
평가 및 의견
입체 공간의 지배 관계
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
입체 공간의 지배 관계