All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Your planet is a perfect sphere with radius R and center at (0, 0, 0). There are N asteroids around the planet. Your task is to find the minimal possible number of asteroids you can observe from some point on the suface of the planet. An asteroid can be observed if it's at least 10-3 above the horizon line at the place of the observation.
The first line of input contains a single integer T, denoting the number of testcases.
The first line of each test case contains two space-separated integers, N and R.
The following N lines contains 3 space-separated integers each: coordinates xi, yi, zi of the corresponding asteroid.
For each test case, output one integer in a new line: the answer for the test case.
- 1 ≤ T ≤ 10
- 1 ≤ R ≤ 10
- R - 1 ≤ |xi|, |yi|, |zi| ≤ 50
- Subtask 1[11 points]: 1 ≤ N ≤ 2
- Subtask 2[89 points]: 1 ≤ N ≤ 150
Input: 1 3 1 2 2 2 0 3 4 4 5 0 Output: 0
Sample explanation:One of the solutions can be: as all the asteroids have positive coordinates, we can choose some point on the surface which lies in the all-negative octant (see octant VII here), and none of the asteroids will be observed.
|Tags||geometry, hard, jan16, pavel1996|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.