2017-11-30
649
В первой строке находятся два числа — количество гвоздей N, 1 < N < 100, и вещественное число R — радиус шляпок гвоздей. Все шляпки имеют одинаковый радиус. Далее располагаются еще N строк, в каждой из которых записана через пробел пара вещественных координат центра очередного гвоздя; координаты не превосходят по абсолютной величине числа 100. Описания гвоздей приводятся в порядке обхода вершин многоугольника по или против часовой стрелки, начиная с произвольного гвоздя. Шляпки разных гвоздей не соприкасаются.
Формат выходных данных
Вывод должен в своей единственной строке содержать вещественное число, округленное до двух знаков после точки, — длину ниточки, натянутой вокруг всех гвоздей.
Пример
Решение:
Сначала рассмотрим случай, когда радиус шляпок равен нулю. Тогда нам достаточно просто просуммировать расстояния между всеми последовательными гвоздями (не забыв соединить последний с первым). Расстояние между точками с номерами k и m равно 
. Теперь посмотрим, как будет вести себя длина ниточки, когда у шляпок появится ненулевой радиус.
|
|
|
Длина части веревочки, не соприкасающейся со шляпкой, будет равна длине веревочки, соединяющей центры гвоздей. Это объясняется тем, что каждый участок между двумя гвоздями лежит на касательной к двум последовательным окружностям (вместе с отрезком, соединяющим центры, и радиусами он образует прямоугольник). Таким образом, нам остается найти длину той части ниточки, которая соприкасается со шляпками, и просуммировать эти числа.
Для каждой из окружностей рассмотрим угол 
вершиной которого является центр окружности, а на сторонах лежат точки касания. Длина ниточки, соприкасающейся со шляпкой, будет равна 
. Суммарный же угол по всем гвоздям будет равен 
, так как многоугольник выпуклый и радиус вектор, задающий положение ниточки, совершает полный оборот.
Отсюда следует, что к сумме расстояний между центрами шляпок следует прибавить число r.
var i, n: longint;
r, s: double;
x, y: array[0..100] of double;
Begin
read(n, r);
s:= 2*pi*r;
for i:= 0 to n - 1 do
read(x[i], y[i]);
for i:= 0 to n - 1 do
s:= s + sqrt(sqr(x[i] — x[(i + 1) mod n]) +
sqr(y[i] — y[(i + 1) mod n]));
write(s:0:2)
end.
В реализации использовалась нумерация элементов массива с нуля, чтобы сделать его “закольцованным” и не обрабатывать отдельно последнюю и первую вершины.
Задача “Обезьяны”
Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a1, либо a2, либо... aS бананов (а1 <a2 <...<aS), а 2-ая при каждом очередном
ходе --либо b1, либо b2, либо... bK бананов (b1 <b2 <...<bK). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a1 (при ходе первой обезьяны) либо b1 (при ходе второй обезьяны)).
|
|
|
Определить может ли выиграть первая обезьяна при наилучших ходах соперницы, которая также стремится выиграть. Все входные данные - натуральные числа.
Решение
Будем обозначать текущую ситуацию в игре парой (S,i), где S количество бананов, оставшихся в куче, перед текущим ходом i-ой обезьяны (i равно 1 или 2).
Для того, чтобы (S,1) была выигрышной для игрока 1, среди возможных ситуаций после его хода (S-a1,2),...,(S-ak,2) должна быть хоть одна проигрышная для игрока 2 (в эту то ситуацию и надо будет перевести игру); если все ситуации выигрышные для игрока 2, то (S,1) - проигрышная для игрока 1 (как бы он не поступал, он все равно проиграет).
Пусть ситуация после хода игрока 1 стала (S',2). Опять же делаем все допустимые ходы из этой позиции и смотрим является ли получившаяся ситуация (S",1) выигрышной, проигрышной или такой, которую мы еще не можем оценить. Если выполняется последняя альтернатива, то из (S",1) мы опять делаем все возможные ходы, анализируем, и т.д.
Если мы в конце концов определили, для кого является выигрышной текущая позиция, то возвращаемся к предыдущему ходу и пытаемся определить, какая позиция для делающего ход и т. д., пока не вернемся к ситуации (L,1).
const l1=200;
s=10;
var a: array [0..l1,1..2] of byte; {в ячейке a[L,i]
хранится информация, кто выигрывает в ситуации (L,i)}
b: array [1..2,0..s] of byte; {массив возможных ходов
первого и второго игроков в b[i,0] хранится число
возможных ходов игрока i}
l,i,j:integer;
Function f(ba:Integer;No: Byte): Byte;
Var i,p,r: Byte; {рекурсивная функция вычисления (L,i)}
Begin {f=i, если в (ba,i) выигрывает i}
if Ba<0 {после хода монет <0?}
Then f:= 3-No {выигрыш игрока с номером 3-Nо}
else if ba=0 {монет = 0?}
then begin {выигрыш No}
f:=No;
a[ba,no]:=no;
end
Else if a[ba,no]<>0 {в этой ситуации мы уже были}
Then F:= a[ba,no] {в ней выигрывает a[ba,no]}
Else
Begin {эту ситуацию мы еще не рассматривали}
r:= 0;
{мы будем делать все возможные ходы}
For i:= 1 to b[No,0] do
if ba-b[no,i]>=0 {если ход возможен, то делаем его}
then r:= r or F(Ba-B[No,i],3-No);
if r=0 then r:=no;
If (No and R)<>0 {есть выигрышный ход?}
Then p:= No {да, (ba,i)=No}
Else p:= 3-No; {нет, (ba,i)=3-No}
A[Ba,No]:=p; {запоминаем эту информацию}
f:=p;
End;
end;
begin
for i:=0 to l1 do
for j:=1 to 2 do A[i,j]:= 0;
write('s=');
readln(b[1,0]); {b[1,0] = количество ходов первого игрока}
for i:=1 to b[1,0] do
begin
write('a',i,'='); {сами ходы}
Readln(b[1,i]);
end;
write('k=');
Readln(b[2,0]); {b[2,0] = количество ходов второго игрока}
For j:= 1 to b[2,0] do
begin
write('b',j,'=');
Readln(b[2,j]); {ввод ходов}
end;
repeat {для данных ходов вводятся значения L}
write('L='); {число бананов}
readln(l);
if f(l,1)=1 {вызов рекурсивной функции-проверки}
then writeln('1-я выиграла')
else writeln('1-я проиграла');
for i:=1 to b[1,0] do {распечатка результатов возможных ходов}
if (l-b[1,i])>=0 {из начальной позиции L}
then writeln('b=',b[1,i],' winner=',a[l-b[1,i],2]);
writeln;
until false;
end.
