Задача B. Чёрная дыра ≡

Условие

В далёкой, далёкой галактике существует Чёрная дыра, которая поглощает звёзды, чтобы увеличить свою массу. Однако, для увеличения массы подходят только новые синие звёзды, а красные массу наоборот уменьшают.

Помогите чёрной дыре поглотить все новые синие звёзды и ни одной красной.

На сцене появляются красные и синие звёзды, все они лежат на “космической материи”. Если вырезать из “космической материи” часть под звёздами, то образуется чёрная дыра и звёзды провалятся в неё.

Необходимо сделать такой вырез в “космической материи”, чтобы в образовавшуюся чёрную дыру упали только синие звёзды.

Гарантируется, что все синие звёзды лежат внутри минимальной описывающей окружности, а все красные снаружи.

Автоматически подсчитывается результат работы вашего решения - изменение массы чёрной дыры. В начале программы оно равно нулю. Каждая синяя звезда повышает изменение массы на единицу, каждая красная уменьшает на единицу.

Вам нужно реализовать класс Solution, находящийся в корне проекта в файле под именем Solution.gd. Другие изменения в проекте учитываться не будут.

Родительский класс SolutionWrapper предоставляет вам следующие методы для решения задачи:

• get_stars() — Возвращает список объектов типа Star. Каждый из них содержит следующие поля: position :Vector3 - позиция звезды в глобальном пространстве, var radius :float - радиус звезды, var type :bool - тип звезды (true - синяя, false - красная).
• get_matter_csg_node() — возвращает находящийся на сцене объект CSGBox3D, являющийся "материей".

Проект здесь, Вам нужно только реализовать класс Solution. Вы можете тестировать свои решения, изменяя данные, содержащиеся в файле input.txt в репозитории проекта.

Подсказка: Задача о наименьшей окружности (minimal enclosing circle и т.д.) имеет единственное решение. Возможность получения радиуса звёзд не используется в его нахождении.

Формат входного файла

Первая строка входного файла содержит N - количество звёзд. Далее следует список из N строк по пять чисел x, y, z, d, type описывающий звёзды (позиция, диаметр, тип). Реализовывать считывание данных с файла input.txt не нужно. Для получения данных используйте функции, доступные в классе Solution.

Формат выходного файла

Выходной файл содержит одно число - масса чёрной дыры после появления. Файл с решением должен содержать реализацию класса Solution. Реализовывать самостоятельно вывод в файл output.txt не нужно.

Ограничения

10 ≤ N ≤ 100

 − 50 ≤ x, y, z ≤ 50

1 ≤ d ≤ 8

Примеры тестов

10
0.0 1.5 0.0 6.0 1
-3.0 1.5 -8.0 6.0 1
-30.0 1.5 25.0 6.0 0
10.0 1.5 -6.0 6.0 1
-45.0 1.5 -30.0 6.0 0
-19.0 1.5 15.0 6.0 1
-3.0 1.5 10.0 6.0 1
40.0 1.5 30.0 6.0 0
40.0 1.5 40.0 6.0 0
40.0 1.5 -40.0 6.0 0

5

11
30.0 1.5 0.0 6.0 1
27.0 1.5 -8.0 6.0 1
40.0 3 -6.0 12.0 1
11.0 1.5 15.0 6.0 1
27.0 1.5 10.0 6.0 1
21.0 1.5 15.0 6.0 1
35.0 1.5 26.0 6.0 0
4.0 1.5 23.0 6.0 0
4.0 1.5 0 6.0 0
50.0 1.5 0 6.0 0
30.0 3 -20.0 12.0 0

6