Алгоритм: Невозможно понять этот вызов программирования

Question

Я не могу понять этот вопрос. Что этот вопрос хочет, чтобы мы нашли и что дано. Может кто-нибудь просто объяснить это наивным образом.

Вопрос

Шериф сообщества хакеров было очень срочное задание сделать. Ему необходимо рассеять все бомбы, наложенные на Joker. Джокер чрезвычайно умный и жестокий. Он выбрал область 1000 X 1000 баллов, выбрал N центральных точек формы (X, Y) и разместил бомбы на каждом интеграле , который был на или внутри круговой области радиуса R вокруг , который выбрал точку. Затем он подошел к каждой такой точке и активировал те бомбы, которые лгали на или внутри, по крайней мере, в двух таких круговых областях.

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

ВХОД:

Первая строка ввода содержит Н. Далее N строк содержат 3 пространство целых числа X Y R, как описано выше.

ВЫВОД:

печати количество активных бомб.

СДЕРЖИВАЮЩИЕ: = N < = 10 = Х, Y, R < = 1000 Примечание:

поиска область для Sheriff представляет собой квадрат с диагональю пункты (1,1) и (1000,1000)

Пример ввода

2 
5 5 2 
3 4 3 

Пример вывода

Объяснение

Все последующие 9 пунктов находятся внутри 2 круга зарегистрировано не менее

3 5 
4 4 
4 5 
4 6 
5 3 
5 4 
5 5 
5 6 
6 4 

Я понятия не имею, как подойти к этому problem.Where сделал джокер растению бомбу и как я должен проверить для этого, есть ли конкретная область бомбить planted.Sorry я мог бы неправильно это тоже.

Answer 1

Существует много способов решить эту проблему. Один из способов - проверить каждую точку в матрице, чтобы увидеть, сколько кругов она находится. Другим способом является сохранение списка точек внутри круга и увеличение счетчика, если точка уже существует.

Answer 2

лучший способ объяснить это, начиная с квадратами ....

себе сетка как таковые:

a 1 2 3 4 5 6 7 
b 1 2 3 4 5 6 7 
c 1 2 3 4 5 6 7 
d 1 2 3 4 5 6 7 
e 1 2 3 4 5 6 7 
f 1 2 3 4 5 6 7 

Допустит, центральная точка была (с, 4), а ширина была 3. Ваш квадрат будет нарисован на точках (b, 3) (b, 4) (b, 5) (c, 3), (d, 3) (d, 4) (d, 5) (c, 5)

(с, 4) будет в середине .....

So ... с площади вы бы 9 (объявление d все точки ребер, которые я описал, и центральную точку, которая содержится в квадрате).

Вас просят сделать то же самое ..... с кругами .... Удачи ...

Answer 3

Самый простой способ объяснить, что хочет, чтобы этот вопрос:

Учитывая список кругов, определяемых центром (X, Y) и радиусом (R), сколько целых точек (т. е. целые числа (1,4) vs (1.1, 4.4)) сетки 1000x1000 находятся в пределах 2 или более эти круги.

Это то, что задают.

Существует много способов решить эту проблему, но это будут разные вопросы.

Самый простой способ - перебрать все 1000х1000 точек, рассчитать расстояние от каждой точки до центра каждого круга, а для тех точек, расстояние которых меньше, чем R для данного круга, добавьте 1. Все точки со значением более 1 будет сообщено.

Это не обязательно самый эффективный алгоритм. Например, если в списке есть 4 круга, вы будете вычислять 4 000 000 расстояний.

Но это сработает.