LCC/Moose '19 Contest 2 J5 - Evan's Wrath

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 1.5s
Python 1.5s
Memory limit: 128M

Problem type

You are given \(N\) spheres in three-dimensional space by Evan. Each sphere is centered at \((x_i, y_i, z_i)\) and has a radius of \(r_i\). Two spheres intersect if there is a non-zero volume that overlaps. This means that two spheres that touch are not considered intersecting.

Out of the \(N\) spheres, you want to choose a subset \(S\) of spheres, such that the no pair of spheres intersect one other, and \(S\) contains the most spheres.

How many spheres are in the largest subset?

Input Specification

The first line will contain the integer \(N\) \((1 \le N \le 22)\).

The next \(N\) lines will each contain four integers, \(x_i, y_i, z_i, r_i\) \((|x_i|, |y_i|, |z_i|, r_i \le 10^8)\).

Output Specification

Output the size of the largest subset \(S\), such that no pair of spheres in the subset intersects one another.


Subtask 1 [20%]

\(N \le 1, x_i, y_i = 0\)

Subtask 2 [10%]

\(N \le 3, x_i, y_i = 0\)

Subtask 3 [20%]

\(x_i, y_i = 0\)

Subtask 4 [50%]

No further constraints.

Sample Input 1

0 0 0 3

Sample Output 1


Explanation For Sample 1

You are given \(1\) sphere centered at \((0, 0, 0)\) having a radius of \(3\). Of course, this sphere can be in the subset. Thus, the size of the largest subset is \(1\).

Sample Input 2

2 3 3 1
3 -5 10 3
0 0 0 5
4 3 0 1

Sample Output 2


Explanation For Sample 2

Note that you do not need to pass this sample to pass some of the subtasks.

The largest subset consists of selecting the first sphere, the second sphere, and the fourth sphere.

This can be seen from the image below:

The red sphere is the first sphere, the orange sphere is the second sphere, the blue sphere is the third sphere, and the green sphere is the fourth sphere.


There are no comments at the moment.