Пользователь вводит число сторон. Надо построить многоугольник с длинами сторон, которые тоже вводит пользователь. Задача не олимпиадная, но интересная.
Lapp
8.02.2011 11:54
Цитата(kumino @ 7.02.2011 21:44)
Пользователь вводит число сторон. Надо построить многоугольник с длинами сторон, которые тоже вводит пользователь. Задача не олимпиадная, но интересная.
Согласен, задача интересная. Какие у тебя мысли по поводу решения?
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
Цитата(TarasBer @ 8.02.2011 20:00)
Ну, во-первых, надо, чтобы самая длинная сторона A была меньше суммы остальных. Остальные стороны разбей на 2 набора B и C так, чтобы разность их длины была меньше, чем длина наибольшей стороны (ну типа просто сначала в один набор засунь всё, потом в другой переноси по одному элементу, пока разница не станет меньше длины наибольшей стороны). А теперь строй треугольник со сторонами длиной A, B и C.
Прикольная идея! А если введено n сторон, а у фигуры должно быть тоже n сторон?
TarasBer
8.02.2011 21:53
Дык а это и есть эн сторон. Просто некоторые из них продолжают друг друга.
kumino
8.02.2011 23:09
Ладно, скажу так: ни одна сторона не должна продолжать другую.
Lapp
16.02.2011 16:58
Я не просто так сказал в начале, задача действительно интересная. Жаль только руки все не доходили до нее..
Интересная она как раз своей неоднозначностью. Если в задаче один ответ - обычно, проблем нет )). Я имею в виду проблемы выбора . А тут, вроде, сразу понятно, что ответов бесконечное количество (причем, мощности континуума, да еще и многомерного)). Но начинаешь решать - упираешься в какие-то странные трудности - какую именно форму выбрать и почему? И надо сказать, что вот это:
Цитата(kumino @ 8.02.2011 19:09)
Ладно, скажу так: ни одна сторона не должна продолжать другую.
- практически не уменьшает проблем..
Поэтому я советую сразу себя ограничить . Если сказать себе: построить многоугольник, вписанный в окружность - все неоднозначности улетучиваются, и остается только сделать построение. Приведенный ниже код это делает. Для поиска радиуса описанной окружности решаем уравнение:
a1 + ... + an = 360o ,
где ai есть угол из центра окружности, опирающийся на 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
Спасибо.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.