Автор: мисс_граффити 18.04.2007 0:12
Здравствуйте!
Посмотрела, какой интерес вызвала тема про отрезки. Предлагаю обсудить другую геометрическую задачу... На мой взгляд, довольно красивую.
Взята отсюда:
http://acm.timus.ru/problem.aspx?space=1&num=1075 (Ural State Univerisity Personal Contest Online February'2001)
Даны три точки в трёхмерном пространстве — A, B и С. Все координаты этих точек — целые и ограничены по модулю числом 1000. Твёрдый шар с центром в точке С прочно закреплён. Радиус шара R — целое положительное число. Расстояния от точки С до точек A и B строго больше R.
Необходимо протянуть из точки А в точку B нитку минимальной длины. Разумеется, эта нитка не может заходить внутрь шара.
Ваша задача — найти длину этой нитки.
Предварительные мысли такие:
1. Переходим от 3D в 2D (рассматриваем плоскость, проходящую через А, В и С)
замечание, дописанное позже: ничего подобного другая плоскость даст меньшую длину
2. Если АВ не пересекает окружность, то длина нитки - вычисленное расстояние между А и В.
3. Если пересекает, то нитка разделится на 3 участка:
1) от точки А до окружности по касательной
2) вдоль окружности между двумя точками касания
3) по касательной до точки В
соответственно, рассматриваем огибание с двух сторон.
Что скажете?
В "олимпиадные.." не стала закидывать, т.к. интересует именно обсуждение.
Автор: klem4 18.04.2007 0:26
Цитата
соответственно, рассматриваем огибание с двух сторон.
У шара то не 2 'стороны' ... Если окружность то да, посмотреть огибание сверху и снизу, а с шаром то не прокатит так...
хотя ... надо воображалку подключать
Автор: Lapp 21.04.2007 8:06
Цитата(мисс_граффити @ 17.04.2007 21:12)
Посмотрела, какой интерес вызвала тема про отрезки.
мисс_граффити, u kiddin'?
Задача про отрезки вызвала
минимум возможного интереса.. Просто когда я сделал ошибку,
volvo меня поправил - вот и весь интерес..
А в результате даже автор (-ша) темы не обратила внимания..
Цитата(мисс_граффити @ 17.04.2007 21:12)
Предлагаю обсудить другую геометрическую задачу...
Дык. А почему тогда тут, в кодинге?
Цитата(мисс_граффити @ 17.04.2007 21:12)
Что скажете?
А скажем, что некоторым админам, особенно из приполярных губерний, надо надевать очки на нос, а не прибавлять их к рейтингу.. Не заметил я этой темы!
Но, уважаемая
мисс_граффити, ты же сама все решила и даже не заспойлерила! Что остается добавить?..
Разве что то, что прямая часть вычисляется простым образом по Пифагору (как катет, а АС и ВС - гиппопотамы). Дуга окружности считается (в градусах) как 180-АСВ.
А что тут еще добавишь?.. Задача явно не на программирование.
Цитата(klem4 @ 17.04.2007 21:26)
У шара то не 2 'стороны' ... Если окружность то да, посмотреть огибание сверху и снизу, а с шаром то не прокатит так...
klem4, прокатит. Кратчайшая из подобных кривых будет лежать именно в плоскости АВС. Остается только выбрать из двух, что Юля и делает.
Так что делать то? Вариантов три:
1. сама переносишь в Математику;
2. кто-то другой это делает;
3. кто-то пишет прогу..
Автор: мисс_граффити 21.04.2007 15:26
Цитата
Дык. А почему тогда тут, в кодинге?
Потому что по сути она геометрическая (как и отрезки), но конечным продуктом должен быть код.
Цитата
Задача явно не на программирование.
Программирование.
Цитата
Дуга окружности считается (в градусах) как 180-АСВ.
Почему???
сначала были мысли, что четвертый тест не проходит из-за погрешности (все-таки на подобных вычислениях она большая). Но по условиям точность должна быть до 2 знаков. Погрешность меньше...
Автор: Lapp 21.04.2007 19:07
Цитата(мисс_граффити @ 21.04.2007 12:26)
Почему???
Упс, ошибочка... Завтра исправлю... если будет необходимость...
PS
мисс_граффити, как тебе удается писать посты без единого смайла?.. поделись секретом.. Даже мои два милых бегемотика тебя не усмехнули..
Автор: мисс_граффити 21.04.2007 19:28
Нашла в алгоритме ошибку Буду исправлять, может, именно в ней дело - неправильно расстояние считаю.
Цитата
мисс_граффити, как тебе удается писать посты без единого смайла?.. поделись секретом..
легко
у меня интернет периодически начинает тормозить по-страшному. Длится это счастье иногда до получаса, приходится отключать картинки, чтобы хоть как-то работало.
про бегемотиков - не поняла.
Автор: Lapp 22.04.2007 2:19
Цитата(мисс_граффити @ 21.04.2007 16:28)
приходится отключать картинки, чтобы хоть как-то работало.
Так ведь, чтоб поставить двоеточие и скобочку - картинок, вроде, не надо..
Цитата(мисс_граффити @ 21.04.2007 16:28)
про бегемотиков - не поняла.
Поищи их.. они там.. прячутся..
)))) маленькие еще.. стесняются....
Автор: мисс_граффити 22.04.2007 3:03
не нашла бегемотиков (
придется ждать, пока подрастут.
я двоеточием со скобочкой часто пользуюсь... и еще вот этим:
Автор: Lapp 22.04.2007 3:08
Цитата(мисс_граффити @ 22.04.2007 0:03)
не нашла бегемотиков
(
Цитата(Lapp @ 21.04.2007 5:06)
по Пифагору (как катет, а АС и ВС - гиппопотамы).
Я так и знал, что мои посты практически не читают...
Автор: мисс_граффити 22.04.2007 3:57
извиняйте.
техника быстрого чтения имеет серьезные недостатки.... *смущенный смайлик*