Модераторы: Alx, Fixin

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] Построение N-угольника, охватывающего все указанные окружности 
V
    Опции темы
KasMP
Дата 3.12.2008, 20:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Цитата
Есть координатная плоскость и непересекающиеся окружности на ней. Координаты центров окружностей известны, все окружности радиуса R.
Нужно найти минимальную длину кривой, которой можно "обтянуть" окружности так, чтобы все они были внутри полученного многоугольника.

Более понятная формулировка. Есть столбики одинакового радиуса. Надо найти минимальную длину веревки, которой можно обтянуть все столбики так, чтобы ни один не остался снаружи.

Примечание. Предполагается активное использование массивов.

Моя голова сломалась smile  smile .
PM MAIL   Вверх
aram90
Дата 3.12.2008, 21:32 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Bug hunter



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 1.12.2008
Где: Yerevan, Armenia

Репутация: 2
Всего: 3



Надо превратит круги в точки, и решить задачу для точек - центров окружностей, потом добавить к нему 2*pi*r, и
получится ответ.
А задачу для точек надо решить методом построения выпуклой оболочки
PM MAIL WWW ICQ   Вверх
maxdiver
Дата 4.12.2008, 09:23 (ссылка) |  (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 2
Всего: 18



Всё так, только непонятно, как в условии согласуется "N-угольник" и "кривая" - это же разные вещи.

Если действительно разрешена произвольная кривая, то метод aram90 правильный. Хотя я когда-то решал эту задачу, и до идеи с 2 pi r не дошёл, и где-то часа полтора писал эту геометрию со всякими дугами, секторами окружностей... smile
PM MAIL WWW ICQ   Вверх
KasMP
Дата 4.12.2008, 09:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Цитата(maxdiver @  4.12.2008,  09:23 Найти цитируемый пост)
Всё так, только непонятно, как в условии согласуется "N-угольник" и "кривая" - это же разные вещи.
smile smile Скажем так: "кривой" я назвала это потому, что это будет не прямая, а совокупность отрезков прямых (т.е. самый настоящий N-угольник в полном смысле этого слова).
Цитата(aram90 @  3.12.2008,  21:32 Найти цитируемый пост)
потом добавить к нему 2*pi*r, и
получится ответ.
2*pi*r - полная длина окружности... А у нас веревка будет соприкасаться лишь с частью столбика (выделено красным на рисунке).
(или это компенсируется засчет того, что центр окружности (случай с точками) находится "дальше", чем сам окружность?
user posted image
Цитата(maxdiver @  4.12.2008,  09:23 Найти цитируемый пост)
и где-то часа полтора писал эту геометрию со всякими дугами, секторами окружностей... smile 
Пока у меня тоже получается эта страшная геометрия...
Цитата(Rodman @  4.12.2008,  09:44 Найти цитируемый пост)
Модератор: Название темы должно содержать язык или область написания!

Это зеркало! Я просила дописать к началу названия зеркала "[Алгоритм]" - внимательный админ сказал, что это, к сожалению, невозможно.

Добавлено через 2 минуты и 17 секунд
Цитата(Rodman @  4.12.2008,  09:44 Найти цитируемый пост)
Модератор: Название темы должно содержать язык или область написания!
А вообще изначально тема была создана в разделе "Алгоритмы" ->  отсутствие "[Алгоритм]" в начале названия хорошо компенсировалось подписью внизу "Зеркало из раздела "Алгоритмы".
PM MAIL   Вверх
THandle
Дата 4.12.2008, 17:03 (ссылка) |  (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: нет
Всего: 372



KasMP, вот точно такая же задача: http://acm.timus.ru/problem.aspx?space=1&num=1020

Я её решил так(за кривость не ругать, тут был важен только результат):

Код

program Project1;

type
  TCoord = record
    X, Y: Real;
  end;
  PCoordArray = ^TCoordArray;
  TCoordArray = Array [0..0] Of TCoord;

function Way(const X1, X2, Y1, Y2: Real): Real;
var
  sqi: Real;
begin
  sqi := (X2 - X1) * (X2 - X1);
  sqi := sqi + (Y2 - Y1) * (Y2 - Y1);
  Way := Sqrt(sqi);
end;

var
  N: Byte;
  R: Real;
  Coords: PCoordArray;
  I: Integer;
  Len: Real;

begin
  ReadLn(N, R);
  GetMem(Coords, SizeOf(Real) * N);
  for I := 0 to N - 1 do
    ReadLn(Coords^[I].X, Coords^[I].Y);
  Len := 0;
  for I := 1 to N - 1 do
    Len := Len + Way(Coords^[I - 1].X, Coords^[I].X, Coords^[I - 1].Y, Coords^[I].Y);
  Len := Len + Way(Coords^[N - 1].X, Coords^[0].X, Coords^[N - 1].Y, Coords^[0].Y);
  Len := Len + 2 * PI * R;
  WriteLn(Len:0:2);
  ReadLn;
end.


То есть по уравнению прямой находим сначала расстояния для точек, а потом прибавляем 2*Pi*R как уже было сказано.
Timus сказал что решено верно))
PM   Вверх
KasMP
Дата 4.12.2008, 20:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



THandle, очень рада твоему участию smile  smile !

Твой код решает задачку с Timus-а, это бесспорно smile (даже ностальгия по паскалю проснулась smile , пока просматривала...).
Но моя задачка и задачка с Timus-а - отнюдь не одно и то же smile smile:
Цитата(Задачка с Timus-а)
...
The nails are described either in a clockwise or in a counterclockwise order starting from an arbitrary nail.
...
Т.е. у Timus-а то, как веревка обтягивает шляпки/столбики/деревья/окружности (другими словами, как построен многоугольник), уже определено. А у меня нет smile .

Моя основная проблема как раз и состоит в том, что я не знаю (пока), как выбрать правильную последовательность вершин (самая правильная та, которая требует самую короткую веревку). Впрочем, надо изучить метод построения выпуклой оболочки smile , рекомендованный aram90 (по названию это походит на то, что нужно).
Задачку с Timus-а я бы решила без проблем сама - сложить длины отрезков несложно smile .

Тем не менее, от задачки с Timus-а есть большая польза smile : я убедилась, что действительно можно сначала рассматривать точки, а потом просто прибавить длину окружности smile (только пока не поняла, как это доказать...).

Добавлено через 1 минуту и 3 секунды
Цитата(aram90 @  3.12.2008,  21:32 Найти цитируемый пост)
А задачу для точек надо решить методом построения выпуклой оболочки 

Большое спасибо за наводку smile, посмотрю smile ...
PM MAIL   Вверх
maxdiver
Дата 4.12.2008, 23:21 (ссылка) |   (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 2
Всего: 18



KasMP, какое-то хитрое условие smile
Но раз получается, что "окружать" сами столбики мы не должны, т.е. дуг не надо, то получается, что 2 Pi R действительно прибавлять не надо, а сама искомая кривая будет представлять собой многоугольник, причём выпуклую оболочку центров окружностей (в этом легко убедиться, достаточно сдвинуть каждый отрезок к центрам обеих окружностей; т.к. в точке касания радиус перпендикулярен отрезку, то никаких "компенсирований" не будет).

Ну а выпуклая оболочка - вообще стандартная вещь.
Например, вот: e-maxx.ru/algo/convex_hull_graham smile
PM MAIL WWW ICQ   Вверх
KasMP
Дата 5.12.2008, 14:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Видимо, я совсем разучилась объяснять...
Цитата(maxdiver @  4.12.2008,  23:21 Найти цитируемый пост)
Но раз получается, что "окружать" сами столбики мы не должны, т.е. дуг не надо
Окружать столбики как раз надоsmile , дуги надо учитывать обязательно  smile !

Еще условие можно сформулировать так smile :
Цитата(Самая понятная формулировка)
Есть лес. В лесу деревья. Стволы всех деревьев входят в землю перпендикулярно и имеют одинаковый радиус R. Даны координаты центров деревьев (в каком угодно порядке - деревья растут так, как им хочется...).
Есть веревка. Ее нужно натянуть вокруг деревье так, чтобы ни одно дерево не осталось снаружи. Найти минимальную длину такой веревки.


Добавлено через 2 минуты и 24 секунды
Цитата(maxdiver @  4.12.2008,  23:21 Найти цитируемый пост)
Ну а выпуклая оболочка - вообще стандартная вещь.
Например, вот: e-maxx.ru/algo/convex_hull_graham smile 

Спасибо за ссылочку smile .
Я вчера нашла другую, где описывается не только метод Грэхема, но и метод Джарвиса smile  smile .
PM MAIL   Вверх
maxdiver
Дата 5.12.2008, 17:51 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 2
Всего: 18



Цитата
Окружать столбики как раз надо , дуги надо учитывать обязательно

Ну раз окружать таки надо, то и прибавлять 2 pi r надо тоже smile
Откуда это берётся - оттуда, что если мы рассмотрим все столбики (не считая тех, что не в выпуклой оболочке), то в сумме эта кривая "накрутит" дуг как раз на полные 360 градусов, т.е. ровно на одну длину окружности. В этом можно убедиться, если мысленно удалить все прямые отрезки кривой, как бы совместив все столбики в один - как раз все дуги кривой сложатся и образуют одну окружность.

Цитата
Я вчера нашла другую, где описывается не только метод Грэхема, но и метод Джарвиса

Если ограничения маленькие, то можно и Джарвиса. Хотя мне всегда казалось, что Грэхэм пишется проще, да и асимптотически в общем случае он лучше.
PM MAIL WWW ICQ   Вверх
KasMP
Дата 5.12.2008, 23:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Итак, алгоритм я полностью поняла smile , за что вам большое спасибо smile .
Рано или поздно я все это реализую и покажу вам результат smile .

К слову, maxdiver, у тебя очень хорошая ссылочка smile - написано коротко, емко и понятно smile , без лишних доказательств очевидного, без ... .
PM MAIL   Вверх
KasMP
Дата 8.12.2008, 12:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Я нелепо споткнулась на самом неожиданном месте, на поиске самой нижней (правой) точки.
У меня 2 функции:
  • LowermostRightPoint.
    По сути, непосредственно оценками она не занимается, она просто помнит текущую лучшую точку и подкидывает новые точки функции PresentFirstPoint, которая и выполняет всю оценивающую работу (короче можно сказать, что LowermostRightPoint координирует действия, выполняет административную функцию).
  • PresentFirstPoint.
      Она получает:
    • ссылку на массив с координатами;
    • индекс точки, которую нужно сравнить с лучшей текущей (i);
    • индекс текущей лучшей точки (res).
    Сначала она смотрит, меньше ли ордината текущей точки, чем ордината лучшей точки. Если меньше, то, естественно, ты запоминаем номер текущей точки как лучший.
    Если не меньше, то проверяем, а не совпадают ли ординаты. Если совпадают, то более чем логично сравнить абсциссы... Лучшая точка та, у которой абсцисса больше.
    Потом  PresentFirstPoint возвращает в своему руководителю LowermostRightPoint номер лучшей на данный момент точки.
По-моему, все идеально. Но работает, как хочет... То правильно, то выбирает правейшую (нижнюю) точку, то вообще левую верхнюю smile  smile .

Код

// часть поиска нижней правой точки: если текущая точка лучше запомненной, то вернуть индекс текущей (иначе вернуть тот же индекс, который был)
short int PresentFirstPoint (short int coordinate[][2], short int i, short int res)
{
      short int present=coordinate[i][1];
      short int res_present=res;
             
      if (present<coordinate[res][1])
         res_present=i;
         else {
              if (present=coordinate[res][1])
                res_present=(coordinate[i][0]>coordinate[res][0] ? i : res);
         }
      
                       
      return (res_present);
}


Код

// поиск нижней правой точки, возвращает ее номер
short int LowermostRightPoint (short int coordinate[][2], short int number)
{
      short int i, k, res;
      short int present1, present2;
      
      /* if (number%2)
         k=number/2;
         else k=number/2-1; 
         это типа объяснение того, как получилась следующая строчка*/
      k=number/2+number%2-1;
      res=0;
      
      for (i=0; i<=k; ++i) {
          res=PresentFirstPoint(coordinate,i         ,res);
          res=PresentFirstPoint(coordinate,number-i-1,res);
      }
        
      return(res);
}


Добавлено через 4 минуты и 31 секунду
Если кто-то решится помочь, то следующее - для вашего удобства smile ...

Код

// ввод координат точек
void InputCoordinate (short int coordinate[][2], short int number)
{
     short int i;
     for (i=0; i<number; ++i) {
         printf ("Input X for %d tree:\n", i+1); scanf ("%d", &coordinate[i][0]);
         printf ("Input Y for %d tree:\n", i+1); scanf ("%d", &coordinate[i][1]);
     }
}


Код

main() {
       
       // ввод кол-ва точек, их координат
       short int   number;
       printf ("Input a number of trees.\n"); scanf ("%d", &number);
       short int   coordinate[number][2];
       printf ("Input coordinates of trees.\n"); InputCoordinate(coordinate,number);

...
}


Добавлено через 7 минут и 18 секунд
Еще быстрая сортировка не сортирует точки в порядке увеличения угла (уменьшения косинуса) массив... Но уж с этим я должна разобраться!!!!!!!!!
PM MAIL   Вверх
THandle
Дата 8.12.2008, 23:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: нет
Всего: 372



KasMP, ох... C++... 

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

Еще, чтобы не возникало подобных тем:
http://forum.vingrad.ru/forum/topic-230265.html

Я сделал зеркало на эту тему во флейм(пока на неделю). Если против этого зеркала имеешь что-то - сразу удалю smile
PM   Вверх
KasMP
Дата 8.12.2008, 23:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Покажи то описание по которому ты пишешь алгоритм. 

Вот smile .
Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Еще, чтобы не возникало подобных тем:

Ок, больше не буду smile smile .
Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Я сделал зеркало на эту тему во флейм(пока на неделю). Если против этого зеркала имеешь что-то - сразу удалю

Удали, пожалуйста smile .

Добавлено через 8 минут и 44 секунды
Вообще говоря, остальные части алгоритма у меня написаны и должны работать (по крайней мере, на мини-тестиках выполнялись правильно).

А вот с на первый взгляд легкой задачкой определения самой нижней (правой) точки творится что-то нереальное! Вот где у меня ошибка? Я прогоняла на бумажечке разные значения всего - все правильно. Может быть, ошибка в каких-то конкретно моих настройках?
PM MAIL   Вверх
THandle
Дата 9.12.2008, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: нет
Всего: 372



Цитата(KasMP @  8.12.2008,  23:16 Найти цитируемый пост)
Ок, больше не буду


Да я не против smile Просто кажется что никто в такие темы не заходит/не переходит по ссылкам.

Цитата(KasMP @  8.12.2008,  23:16 Найти цитируемый пост)
Удали, пожалуйста 


Ок.


В общем - делаю сейчас прожку. Для наглядности все точки выводим в виде рисунка на экран(типа как в описании алгоритма).
Получилось найти первый элемент и отсортировать массив. Остальное буду пробовать сделать вечером...
PM   Вверх
KasMP
Дата 9.12.2008, 12:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30



Напишу заголовки моих функций (вдруг ты решишь организовать свои подобным образом smile - будет проще сравнивать smile )...

Код

// ввод координат точек
void InputCoordinate (short int coordinate[][2], short int number)

// часть поиска нижней правой точки: если текущая точка лучше запомненной, то вернуть номер текущей точки
short int PresentFirstPoint (short int coordinate[][2], short int i, short int res)

// поиск нижней правой точки; возвращает ее номер
short int LowermostRightPoint (short int coordinate[][2], short int number)

// возвращает косинус угла между векторами first_i и (1,0)      
float Angle_First_OX (short int coordinate[][2], short int i, short int first_x, short int first_y)

// обменивает местами элементы [i][0] и [j][0], [i][1] и [j][1] массива array
void Swap (float array[][2], short int i, short int j)
/* нужно для двумерного массива, у которого
[i][0] - значения косинусов углов между векторами (first; i) и (1,0)
[i][1] - индекс соответствующей точки */

// быстрая сортировка массива array
void Quicksort (float array[][2], short int left, short int right)

// определяет, образуют ли точки 1-2-3 левый поворот (true - поворот левый)
bool LeftSwerve (short int x1, short int y1, short int x2, short int y2, short int x3, short int y3)

// возвращает расстояние между точками (x1,y1) и (x2,y2)
float Distance (short int x1, short int y1, short int x2, short int y2)

// возвращает периметр многоугольника из точек, индексы которых хранятся в стеке stack[number]; 
float Perimeter (short int stack[], short int coordinate [][2], short int number)


Добавлено через 48 секунд
Цитата(THandle @  9.12.2008,  12:01 Найти цитируемый пост)
Да я не против smile Просто кажется что никто в такие темы не заходит/не переходит по ссылкам.

Как показывает опыт, переходят и даже думают (а иногда де отвечают) smile !
Цитата(THandle @  9.12.2008,  12:01 Найти цитируемый пост)
Ок.

Спасибо smile .
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема »


 




[ Время генерации скрипта: 0.1041 ]   [ Использовано запросов: 23 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.