Wcipeg 2018 ECOO Qualifier

Shattering Shadows 2

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 ≤ N ≤ 100000) 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 is at most 1000.

Input Format:

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 -1000 to 1000, representing one shadow. No shadow will be located at point (0, 0, 0).

Output Format:

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

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jan 28, 2018
Author: imaxblue

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)