Командный чемпионат мира по программированию. Задача G

[Pavlovsky]

Для чистоты доказательства, надо еще доказать:
Из любого набора длин сторон S1,S2,...,Sn (кроме вырожденных случаев, когда длина одной из сторон больше или равна сумме других сторон) можно построить многоугольник вписанный в окружность.

[age]

age в сообщении #453022 писал(а):

Хотя нет, Вы, Equinoxe и sup правы. Его стороны по 1 можно прибавить к двум сторонам по 10, тогда получится выпуклый четырёхугольник со сторонами $10,10,11,11$. Если так можно?

Да нет. Для предложенного мной примера 4 стороны по 10 и 2 по 1, максимальную площадь имеет 6-угольник:


Его площадь приблизительно равна $111.2785>110$ - больше площади прямоугольника $11\times10$.

Ну-ка впишите его в окружность. Либо представьте вписанный с теми же сторонами, но площадью $>111.2785$

-- Чт июн 02, 2011 17:41:45 --

Нет, ошибся, нашёл вот такой:


$S=100+10\sqrt2>114$

[caxap]

Я в GeoGebra набросал. Площадь получилась $\approx 114{,}5$.

$$\definecolor{zzttqq}{rgb}{0,0.4,0} \definecolor{xdxdff}{rgb}{0,0,0} \definecolor{qqqqff}{rgb}{0,0,0} \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.3cm,y=0.3cm] \clip(-6.41,-9.55) rectangle (10.54,6.95); \fill[color=zzttqq,fill=zzttqq,fill opacity=0.1] (-3.48,3.23) -- (-2.82,3.98) -- (7.18,4) -- (7.91,3.33) -- (7.31,-6.69) -- (-2.69,-6.74) -- cycle; \draw [color=zzttqq] (-3.48,3.23)-- (-2.82,3.98); \draw [color=zzttqq] (-2.82,3.98)-- (7.18,4); \draw [color=zzttqq] (7.18,4)-- (7.91,3.33); \draw [color=zzttqq] (7.91,3.33)-- (7.31,-6.69); \draw [color=zzttqq] (7.31,-6.69)-- (-2.69,-6.74); \draw [color=zzttqq] (-2.69,-6.74)-- (-3.48,3.23); \draw(2.24,-1.36) circle (2.2cm); \fill [color=qqqqff] (-3.48,3.23) circle (1.5pt); \fill [color=xdxdff] (-2.82,3.98) circle (1.5pt); \fill [color=xdxdff] (7.18,4) circle (1.5pt); \fill [color=xdxdff] (7.91,3.33) circle (1.5pt); \fill [color=xdxdff] (7.29,-6.65) circle (1.5pt); \fill [color=xdxdff] (-2.69,-6.74) circle (1.5pt); \fill [color=xdxdff] (7.31,-6.69) circle (1.5pt); \fill [color=qqqqff] (2.24,-1.36) circle (1.5pt); \fill [color=qqqqff] (4.33,-8.39) circle (1.5pt); \end{tikzpicture}$$

[Pavlovsky]

age в сообщении #453046 писал(а):

Нет, ошибся, нашёл вот такой:


$S=100+10\sqrt2>114$

Сегодня явно не ваш день. Это не максимальный многоугольник. У максимального обозначенный вами угол будет чуток больше 45 градусов.

[age]

Pavlovsky в сообщении #453095 писал(а):

Сегдня явно не ваш день. Это не максимальный многоугольник. У максимального обозначенный вами угол будет чуток больше 45 градусов.

Ну главное, что интересную задачу решили.

[Pavlovsky]

Кстати на чемпионате эту задачу решили только 7 команд из 105 команд участников.