Версия для печати темы

Автор: kumino 8.02.2011 1:44

Пользователь вводит число сторон. Надо построить многоугольник с длинами сторон, которые тоже вводит пользователь. Задача не олимпиадная, но интересная.

Автор: Lapp 8.02.2011 11:54

Согласен, задача интересная.
Какие у тебя мысли по поводу решения?

Автор: kumino 8.02.2011 20:44

Может, что-то связанное с пропорциональным делением суммы углов.Не знаю.

Автор: TarasBer 8.02.2011 21:00

Ну, во-первых, надо, чтобы самая длинная сторона A была меньше суммы остальных.
Остальные стороны разбей на 2 набора B и C так, чтобы разность их длины была меньше, чем длина наибольшей стороны (ну типа просто сначала в один набор засунь всё, потом в другой переноси по одному элементу, пока разница не станет меньше длины наибольшей стороны).
А теперь строй треугольник со сторонами длиной A, B и C.

Автор: kumino 8.02.2011 21:22

Прикольная идея! А если введено n сторон, а у фигуры должно быть тоже n сторон?

Автор: TarasBer 8.02.2011 21:53

Дык а это и есть эн сторон. Просто некоторые из них продолжают друг друга.

Автор: kumino 8.02.2011 23:09

Ладно, скажу так: ни одна сторона не должна продолжать другую.

Автор: Lapp 16.02.2011 16:58

Я не просто так сказал в начале, задача действительно интересная. Жаль только руки все не доходили до нее..

Интересная она как раз своей неоднозначностью. Если в задаче один ответ - обычно, проблем нет )). Я имею в виду проблемы выбора . А тут, вроде, сразу понятно, что ответов бесконечное количество (причем, мощности континуума, да еще и многомерного)). Но начинаешь решать - упираешься в какие-то странные трудности - какую именно форму выбрать и почему? И надо сказать, что вот это:

- практически не уменьшает проблем..

Поэтому я советую сразу себя ограничить . Если сказать себе: построить многоугольник, вписанный в окружность - все неоднозначности улетучиваются, и остается только сделать построение. Приведенный ниже код это делает. Для поиска радиуса описанной окружности решаем уравнение:

где a_i есть угол из центра окружности, опирающийся на i-ю сторону. Углы можно вычислять как удвоенные (добавлено позже) арксинусы отношения половины длины стороны к искомому радиусу (в Паскале, конечно, приходится через арктангенс). В нем единственная неизвестная величина - радиус. Решаю я его обычной дихотомией (вряд ли тут нужен более эффективный метод). А собственно построение - это просто расстановка точек на окружности под нужными углами.

uses Graph;

const
  m= 100;

var
  l: array [1..m] of double;
  i,n,gd,gm: integer;
  r,r1,r2,a,d,cx,cy: double;


begin
  Randomize;
  gd:=0;
  InitGraph(gd,gm,'');
  cx:= GetMaxX/2;
  cy:= GetMaxY/2;
  n:=10;
  for i:=1 to n do l[i]:= Random*cy/2;
  for i:=1 to n do Write(l[i]:6:2);
  WriteLn;
  r1:=0;
  r2:=0;
  for i:=1 to n do begin
    r2:= r2+l[i];
    if l[i]>r1 then r1:=l[i]
  end;
  r2:=r2/4;   // оценка радиуса сверху
  r1:=r1/2;   // оценка радиуса снизу
  repeat
    r:= (r1+r2)/2;
    a:=0;
    for i:=1 to n do a:= a+ArcTan(l[i]/2/Sqrt(Sqr(r )-Sqr(l[i]/2)));
    if a>Pi then r1:=r else r2:=r
  until Abs(r2-r1)<1e-12;
  WriteLn('r = ',r:6:2);
  MoveTo(Round(cx+r),Round(cy));
  for i:=1 to n do begin
    a:= a+ArcTan(l[i]/2/Sqrt(Sqr(r )-Sqr(l[i]/2)));
    LineTo(Round(cx+r*Cos(2*a)),Round(cy+r*Sin(2*a)));
  end;
  ReadLn;
  CloseGraph
end.

Автор: Гость 16.02.2011 22:55

Спасибо.