IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> трехмерное пространство, найти радиус
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


В трехмерном пространстве задано N шаров. Найти шар минимального радиуса, охватывающий все заданные
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Есть задача решенная - найти окружность, в которую вместяться все точки на плоскости.
Расширяем задачу на 3d , получаем найти шар....
И потом добавляем к точкам уловие того, что они имеют размер.
Таким образом задача решается.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






<...>
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


volvo, давай рассмотрим частный стучай.
Две сферы, одна с центром в точке (-1,-1,-1), а другая в (1,1,1). Радиусы обеих сфер нулевые. Твой алгоритм даст диаметр, равный 2. На самом же деле он равен Sqrt(3).

Сообщение отредактировано: lapp -


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Ну, во-первых, не Sqrt(3), а 2*Sqrt(3)

Если уже взялся что-то опровергать, то делай это ПРАВИЛЬНО.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(volvo @ 23.04.2006 12:55) *

Ну, во-первых, не Sqrt(3), а 2*Sqrt(3)

Если уже взялся что-то опровергать, то делай это ПРАВИЛЬНО.

Извиняюсь. Ошибся. 2*Sqrt(3). И вовсе незачем кричать.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


А есть данные для теста ? А то вот накатал кое что а проверить не могу ;)


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


В общем вот что пока есть.На соклько я вижу отличается от того что предложил вольво, но возможно тоже имеет место быть smile.gif ... и всетаки было-бы не плохо увидеть тестовый пример smile.gif

{$N+}
uses crt;
const
n = 5;
type

TSphere = record
x, y, z, r : word;
end;

TSArr = array [1..n] of TSphere;

procedure Fill(var s : TSArr);
var
i : word;
begin
for i := 1 to n do
with s[i] do begin
write(i , ').');
readln(x, y, z, r);
end;
end;

function Len(P1, P2 : TSPhere) : single;
begin
Len := sqrt
(
(P2.x - P1.x) * (P2.x - P1.x) +
(P2.y - P1.y) * (P2.y - P1.y) +
(P2.z - P1.z) * (P2.z - P1.z)
);
end;

function IsIncludeAll(s : TSArr; m : word) : boolean;
var
i : word;
begin
i := 1;
while (i <= n) and (Len(s[i], s[m]) + s[i].r <= s[m].r)
do inc(i);
IsIncludeAll := (i > n);
end;


function Find(s : TSArr) : word;
var
i, min : word;
begin
min := 0;
i := 1;
while (i <= n) do begin
if IsIncludeAll(s, i) then
min := i;
inc(i);
end;
Find := min;
end;

var
Sp : TSArr;

begin
clrscr;
Fill(Sp);
writeln(Find(Sp));
readln;
end.




гыя вообще не то что надо решил smile.gif)))

Volvo, ага тока щас понял smile.gif) Еще ведь долго думал как это может быть минимальная среди имеющихся, которая охватыет все остальные :D


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






klem4, ты, если я не ошибаюсь, решаешь несколько другую задачу? Ты пытаешься найти сферу из тех, что заданы?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Вот такой вариант ... но опятьже нужен тестовые данные ... Вариант годится для случая елси центр хотябы одной сферы не совпадает с центрами остальных, в противном случае берем просто наибольший радиус + 1 ...

{$N+}
uses crt;
const
n = 2;
type

TSphere = record
x, y, z, r : word;
end;

TSArr = array [1..n] of TSphere;

procedure Fill(var s : TSArr);
var
i : word;
begin
for i := 1 to n do
with s[i] do begin
write(i , ').');
readln(x, y, z, r);
end;
end;

function Len(P1, P2 : TSPhere) : word;
begin
Len := round(sqrt
(
(P2.x - P1.x) * (P2.x - P1.x) +
(P2.y - P1.y) * (P2.y - P1.y) +
(P2.z - P1.z) * (P2.z - P1.z)
));
end;

function GetRadius(s : TSArr) : word;
var
i, j, p1, p2, L: word;
maxL : integer;
begin
maxL := -maxint;
for i := 1 to n - 1 do
for j := i + 1 to n do begin
L := Len(s[i], s[j]);
if L >= maxL then begin
maxL := L;
p1 := i;
p2 := j;
end;
end ;

GetRadius := maxL + s[p1].r + s[p2].r;
end;

var
Sp : TSArr;

begin
clrscr;
Fill(Sp);
writeln(GetRadius(Sp));
readln;
end.



К сожалению решение не верное =(


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 39
Пол: Мужской
Реальное имя: Василий

Репутация: -  -2  +


smile.gif klem4, как видно из твоего кода, ты находил две сферы, которые расположены дальше всего друг от друга. Да, такой вариант неверен. Я сегодня долго думал над этой интересной задачкой и для наглядности сначала делал с окружностями, типа в 2D smile.gif Так вот в таком варианте как у тебя бывают случаи (окружности задаются случайно), что какая-то окружность может даже ЦЕЛИКОМ выйти за "охватывающую" окружность. smile.gif Ну, например, чтобы найти окружность, охватывающую множество точек, нужно найти две максимально удаленные точки M и N, найти еще одну точку, максимально удаленную от отрезка MN, и построить по этим трем точкам окружность. Наша же задача сводится к задаче "найти окружность, охватывающую множество окружностей" (2D перевести в 3D не представится сложным). Так вот вопрос: как найти точки A, B и C на прилагаемом мной рисунке?


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






<...>
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Бравый генерал @ 23.04.2006 23:20) *

Наша же задача сводится к задаче "найти окружность, охватывающую множество окружностей" (2D перевести в 3D не представится сложным). Так вот вопрос: как найти точки A, B и C на прилагаемом мной рисунке?

Генерал, мне кажется, что ты ошибаешься с утверждением "перевести в 3D не представится сложным". Нахождение окружности, касающейся трех заданных, называется "задачей Апполония". Решение ее не очень простое, но существует. Но я не уверен, что оно есть для 3D. В 3D три заданных окружности превращаются в четыре заданных сферы..

Но дело даже не в этом. Боюсь, что даже найдя "сферу Апполония" (экстраполяция моя), задачу мы не решим..

P.S.
А куда исчезли мои предыдущие посты из этой темы?..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Автооответчик
*****

Группа: Пользователи
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

Репутация: -  16  +


Цитата
P.S.
А куда исчезли мои предыдущие посты из этой темы?..

почему-то скрыты...

Я тоже не понял почему. Если я что-то не так понял, модераторы поправлят снова.
Пока посты все опубликовал. Altair


Сообщение отредактировано: Altair -


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Я скрыл решение просто по тому что оно не верное, точнее не то я решал что нужно (в общем смысла в них не было), может и не стоило скрывать ...

Вот поправил ф-ю, теперь больше похоже на правду ... ждем тестовые данные ...

function GetRadius(s : TSArr) : word;
var
i, j, p1, p2, L: word;
maxL : integer;
begin
maxL := -maxint;
for i := 1 to n - 1 do
for j := i + 1 to n do begin
L := Len(s[i], s[j]) + s[i].r + s[j].r;
if L >= maxL then begin
maxL := L;
p1 := i;
p2 := j;
end;
end ;

GetRadius := maxL;
end;


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


а ты можешь выложить результат?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Цитата
а ты можешь выложить результат?


Извини, не понял тебя ...


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


я про данные она правильно работает? и ты можешь прислать решение я сравню его со своим...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Я же писал, у меня нету нормальных тестовых данных, сочинать их у меня нет ни малейшего желания, если у тебя они есть выложи их, кстате что тебе мешает самому проверить правильность моей программы ? Я не понимаю.

Сообщение отредактировано: klem4 -


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klem4 @ 25.04.2006 15:41) *

Я скрыл решение просто по тому что оно не верное, точнее не то я решал что нужно (в общем смысла в них не было), может и не стоило скрывать ...
Вот поправил ф-ю, теперь больше похоже на правду ... ждем тестовые данные ...

klem4, ты не обратил внимания на пост Бравого генерала, а он дело говорил. Вот простой пример, опровергающий твое решение.
Код
Сфера 1:  x=-10  y=0   z=0  r=1
Сфера 2:  x=10   y=0   z=0  r=1
Сфера 3:  x=0    y=12  z=0  r=1

Твоя прога найдет 1 и 2 сферы, как наиболее удаленные, и проведет сферу радиусом 11 из начала координат. Сфера 3 в нее не попадет.

Цитата(Бравый генерал @ 23.04.2006 23:20) *

чтобы найти окружность, охватывающую множество точек, нужно найти две максимально удаленные точки M и N, найти еще одну точку, максимально удаленную от отрезка MN, и построить по этим трем точкам окружность.

Бравый генерал, я сначала пропустил это, а сейчас перечитал и увидел: твое утверждение неверно. Вот опровергающий пример.
Код
Точка 1 x=-100  y=0
Точка 2 x=100   y=0
Точка 3 x=0     y=150
Точка 4 x=95    y=-6

Точки 1 и 2 максимально удалены. Т 3 отстоит на максимальное растояние от отрезка 1-2. Окружность, проведенная через 1-2-3 оставит Т 4 снаружи.. (Извиняюсь за некрасивые числа - подбирал в уме)

Забегая вперед, скажу, что я, кажется, решил эту задачу.. smile.gif Как только будет время - напишу сюда решение. Но только в общем виде, без программного кода..

PS
мужики (и дамы тоже!), давайте не прятать ничего и не скрывать. Дискуссия есть дискуссия. Возможны ошибки, возможны неверные рассуждения, неверные понимания - что ж с того? Но среди всего этого рождается Истина! smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name