Я пытался ответить на этот вопрос уже несколько месяцев, но я все еще застрял.
Вопрос требует от меня написать программу для вывода ДА или НЕТ на предмет наличия в данном наборе строки, которая может разделитьэто.
Я ищу возможный алгоритм для определения ответа, я хочу интерпретировать его в код, как только я твердо понимаю ответ.
При заданном наборе кругов равной длинына 2D плоскости, которые гарантированно не касаются.определить, можно ли провести линию через множество, разделив ее ровно на две части, не пересекая ни одной окружности.
- Радиус окружности больше нуля
- Ни одна окружность не касается или не содержит друг друга
- Всегда возможен набор длины 2
- каждый круг может быть уникальным по размеру
Формат ввода:
N - number of circles in set
x y r - N lines of: x coordinate, y coordinate, radius
Input repeats until EOF
Выход YESили НЕТ для каждого теста
Пример ввода:
4
0 0 20
0 40 20
0 30 10
40 -30 10
4
0 0 20
0 40 20
20 40 20
20 -40 20
Вывод:
YES
NO
Редактировать: Мои попытки решить
Первая попытка состояла в том, чтобы найти все линии, которые могли бы решить эту проблему, если бы каждый круг был точками нулевого радиуса, чтобы дать мне ряд возможных решений проблемы.
Ссылка на Разделениеплоскость точек на две равные половины
После этого я возвращал радиусы, а затем перебирал каждое возможное решение.
Этот алгоритм был очень медленным (я не удосужился вычислитьВремя O с требуемого алгоритмадолжен был работать в течение разумного промежутка времени)
My Вторая попытка состояла в том, чтобы спроецировать эти круги на оси y и x и вращать набор, пока не былосечение оси x или y без «тени» какого-либо круга при разбиении наборов на две части.
Этот метод потребует только максимального поворота в 1 / 2pi радиан, чтобы определить ответ, но попытки программирования были сложными и медленными.
Я нигде не могу найти вопрос в Интернете, поскольку он был представлен на бумаге в прошлом году, созданным профессором в моем университете.