Форум программистов, компьютерный форум CyberForum.ru

Геометрическая задача - невозможность достич цели - C++

Восстановить пароль Регистрация
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.01.2013, 17:52     Геометрическая задача - невозможность достич цели #1
Формат данные: круги
Область данных: 2D-поверхность, ограниченная прямоугольником
Входные данные: радиус цели и его центр, радиус объекта (который должен достич цели), его центр и скорость, данные препятиствий (радиусы и их центры)
Дополнительная информация: шар эластично отбивается от препятствий и стен

Выходные данные: YES/NO (может ли объект пересечься с целью по прошествии любого времени?)
Миниатюры
Геометрическая задача - невозможность достич цели  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2013, 17:52     Геометрическая задача - невозможность достич цели
Посмотрите здесь:

C++ Геометрическая прогресия
C++ Программа угадывания случайно выбранных координат цели
Невозможность ввода значения второй переменной C++
C++ Какие цели использования ссылок в C++?
Геометрическая задача C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.01.2013, 17:54  [ТС]     Геометрическая задача - невозможность достич цели #2
Я, если честно, без понятия, как решить, кроме того, чтобы просчитывать всё до тех пор, пока переменная-счетчик для времени не переполнится.. Но вполне может быть, что в момент времени INT_MAX+1 произойдет захват цели, поэтому способ перебора не прокатит никак..
Pure
 Аватар для Pure
228 / 49 / 2
Регистрация: 13.03.2012
Сообщений: 453
Записей в блоге: 7
22.01.2013, 18:02     Геометрическая задача - невозможность достич цели #3
nexen, так это без графики? вычислительная?
обычно окружность является вписанной в некий прямоуголник - BoundRectangle.
В теории решение такое.
если меж препятствиями от которых он эластично отбивается есть проход достаточной ширины для его пролезания мимо них, то рано или поздно объект выйдет из сектора отскоков и попадет таки в цель.
Осталось лишь посчитать "достаточную ширину" коридора, чтобы дать ответ ДА или НЕТ
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.01.2013, 18:16  [ТС]     Геометрическая задача - невозможность достич цели #4
Я тоже так думал, но потом понял, что нет никаких оснований полагать, что шарик через t=184128481875912лет не зациклится и всё-таки не пройдет сквозь одну из 10 щелей.. Более того, таким способом довольно не тривиально разобраться с решеткой (когда препятствия меньшего радиуса, чем объект, стоят так же, как черные клетки на шахматной доске)

Задача вычислительная

p.s Если брать прямоугольники, то в некоторых случаях ответ будет не правильный.
Yandex
Объявления
22.01.2013, 18:16     Геометрическая задача - невозможность достич цели
Ответ Создать тему
Опции темы

Текущее время: 12:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru