Задача
В пространстве задано K сфер. Каждая сфера определяется радиусом R и координатами центра (x, y, z). Найдите все точки пространства с целочисленными координатами, которые лежат ровно внутри N сфер. В качестве ответа выведите число таких точек. Считается. что точка лежит внутри сферы тогда и только тогда, когда расстояние от точки до центра сферы строго меньше радиуса.
Пояснения.
Пусть S - сфера радиуса 5 с центром в точке O (1,2,3). Точка А (1, 6, 6) принадлежит поверности сферы S и не является "внутренней".
Точка B(2, 0, 4) будет "внутренней" точкой сферы S, а точка C (6,3,3) для сферы S будет внешней
Входные данные
В первой строке записаны натуральные числа K и N. (0<N<=K<=10)
Следующие K строк содержат по 4 целых числаx: R, x, y, z. Все числа по модулю не превосходят 100, R - натуральное число.
Выходные данные
Одно число - ответ на задание
Примеры
Входные данные |
Выходные данные |
Пояснение |
1 1
1 5 -7 8 |
1 |
Задана 1 сфера. Требуется найти количество "внутренних" точек сферы радиуса 1.
Такая точка одна - ( 5; -7; 8)
|
1 1
2 3 5 7 |
27 |
Задана 1 сфера. Требуется найти количество "внутренних" точек сферы радиуса 2.
Это точки вида ( 2/3/4; 4/5/6, 6/7/8) |
3 3
2 1 1 1
2 2 2 2
2 3 3 3 |
1 |
Подходит только точка с координатами (2,2,2) |