Олимпиады

Задача “Эчпочмаки”

С приближением холодов любимая крыса Василия Федоровича решила готовить запасы на зиму. На ее радость, Василий Федорович неожиданно решил продемонстрировать свое кулинарное мастерство и приготовил N эчпочмаков, оставив их на некоторое время без присмотра.

В системе жизненных ценностей крысы эчпочмак определяется как треугольник, заданный длинами своих сторон (ввиду отсутствия кулинарного мастерства у Василия Федоровича эчпочмаки получались в виде произвольных невырожденных треугольников). Основное качество эчпочмака по логике крысы — это его площадь (чем больше площадь, тем более ценен эчпочмак).

Крыса была бы рада утащить себе в гнездо, свитое в полости дивана, самый ценный эчпочмак целиком, но прогрызенная ею щель имеет ограниченные размеры, и туда могут пролезть не все эчпочмаки. Щель задается своей шириной D (вещественное число) в сантиметрах. Эчпочмак может быть ориентирован произвольно в плоскости отверстия, и если хотя бы в одном положении он проходит в щель, то он считается подходящим.

Необходимо найти номер наиболее ценного эчпочмака, который проходит в отверстие.

Формат входных данных

Во входном файле записано целое число N — количество эчпочмаков (1 Ј N Ј 1000) и вещественное число D (с точностью до 4 знаков после точки, 0 < D Ј 1000). Далее записаны N троек вещественных чисел Ai, Bi, Ci, задающих длины сторон эчпочмаков (с точностью до 4 знаков после точки, 0 < Ai, Bi, Ci Ј 1000).

Формат выходных данных

В выходной файл выведите номер наиболее ценного эчпочмака, который проходит в щель. Если существует несколько различных правильных ответов, то выведите любой из них. В случае, если ни один эчпочмак протащить невозможно, выведите 0.

Решение

Введем ось x, направленную перпендикулярно прямой, содержащей отверстие. Произвольно ориентируем треугольник в плоскости и начнем двигать его вдоль оси x. Введем функцию d(x), значение которой равно длине отрезка, лежащего в треугольнике на прямой, содержащей отверстие.

Несложно доказать, что с момента прохода вершины A и до момента достижения вершины B функция d(x) будет возрастающей, а затем, до вершины C — убывающей (при доказательстве можно воспользоваться подобием треугольников). Из этого следует, что своего максимума функция d(x) достигнет, когда точка B (средняя вершина треугольника) будет лежать на прямой. То есть, чтобы проверить, проходит ли треугольник при такой ориентации сквозь отверстие, достаточно посчитать значение функции d(x) в средней вершине и проверить, что оно не больше размеров отверстия.

Определимся с наилучшей ориентацией треугольника. Один конец отрезка, задающего пересечение прямой и треугольника, является средней вершиной этого треугольника, а второй лежит на противоположной стороне треугольника. Кратчайшее расстояние от вершины треугольника до его противоположной стороны — это высота этого треугольника. Отсюда понятно, что треугольник надо ориентировать так, чтобы его наименьшая высота была параллельна прямой, содержащей отверстие.

Для вычисления площади треугольника можно воспользоваться формулой Герона

где a, b, c — длины сторон треугольника, а p — его полупериметр. Длину наименьшей высоты можно вычислить, пользуясь формулой для площади треугольника S = 1/2•h•a, где a — наибольшая сторона. То есть h = 2•S/a, где a — наибольшая сторона.

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

var i, n, bestno: longint;

a, b, c, p, s, d, h, bests: double;

begin

read(n, d); bestno := 0; bests := -1;

for i := 1 to n do begin

read(a, b, c);

p := (a + b + c) / 2;

s := sqrt(p*(p-a)*(p-b)*(p-c));

if b > a then a := b;

if c > a then a := c; h := 2*s/a;

if (h <= d) and (s > bests) then begin

bestno := i; bests := s

end

end;

write(bestno)

end.

Задача “Ниточка”

Злоумышленники варварски вбили в ни в чем неповинную плоскую поверхность N гвоздей, да так, что только шляпки остались. Мало того, они в своих подлых целях вбили все гвозди в вершины выпуклого многоугольника. После этого они... страшно сказать... они натянули ниточку вокруг всех гвоздей, так, что поверхности стало совсем грустно!

Ваша задача — определить длину этой ниточки.

Формат входных данных

В первой строке находятся два числа — количество гвоздей 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.

В реализации использовалась нумерация элементов массива с нуля, чтобы сделать его “закольцованным” и не обрабатывать отдельно последнюю и первую вершины.