WCIPEG 2018 ECOO Qualifier P3 - Shattering Shadows 2

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
WCIPEG 2018 ECOO Qualifier

Kanade was not really satisfied with last year's scores on the problem "Shattering Shadows". Specifically, no one solved it! Thus, she decided to torture the students who failed it by giving them the exact same problem but in three dimensions.

There are N (1 \le N \le 200\,000) shadows, represented by points, on a 3-dimensional coordinate plane. Kanade is located at the origin (0, 0, 0) and can shoot an arrow in any direction. However, some shadows might be blocked by other shadows, which Kanade is not able to hit. Count how many shadows Kanade can shoot.

For 90% of cases, N \le 1\,000.

Input Specification

Line 1: T, the number of test cases.

Each case consists of the following: An integer N, the number of shadows. N lines, each with 3 integers x, y, z, between -1\,000 to 1\,000, representing one shadow. No shadow will be located at point (0, 0, 0).

Output Specification

For each case, output the number of shadows that can be hit on a separate line.

Sample Input

3
4
10 10 10
-5 -5 -5
0 0 -1
1 1 1
6
-1 0 0
1 0 0
0 -1 0
0 1 0
0 0 -1
0 0 1
3
1 1 1
1 1 1
1 1 1

Sample Output

3
6
1

Comments

There are no comments at the moment.