Задачи, требующие знаний из геометрии

ЗАДАЧА №894 Кольцо

(Время: 1 сек. Память: 16 Мб Сложность: 16%)

Заданы площадь кольца и радиус внешней окружности. Требуется определить радиус внутренней окружности.

Входные данные Входной файл INPUT.TXT содержит два положительных вещественных числа: S и R₁ – площадь кольца и радиус внешней окружности соответственно. Радиус внешней окружности не превышает 100.

Выходные данные В выходной файл OUTPUT.TXT выведите радиус внутренней окружности R₂ с точностью не худшей, чем 10^-3.

begin
  var (s, r) := ReadReal2;
  Write(Sqrt(r * r - s / Pi):0:3)
end.

Формула площади кольца изучается в школьной геометрии. $$S=\pi\left(R_1^2-R_2^2\right) \quad \to \quad R_2=\sqrt{R_1^2-\frac{S}{\pi}}$$

Для представления данных выбран тип real.

ЗАДАЧА №688 Суслик и собака

(Время: 1 сек. Память: 16 Мб Сложность: 19%)

На большом поле находятся суслик и собака. Собака хочет суслика съесть, а суслик хочет оказаться в безопасности, добежав до одной из норок, выкопанных в поле. Ни собака, ни суслик в математике не сильны, но, с другой стороны, они и не беспросветно глупы. Суслик выбирает определенную норку и бежит к ней по прямой с определенной скоростью. Собака, которая очень хорошо понимает язык телодвижений, угадывает, к какой норке бежит суслик, и устремляется к ней со скоростью вдвое большей скорости суслика. Если собака добегает до норки первой (раньше суслика), то она съедает суслика; иначе суслик спасается.

Требуется написать программу, которая поможет суслику выбрать норку, в которой он может спастись, если таковая существует.

Входные данные Во входном файле INPUT.TXT записано в первой строке два числа – координаты суслика. Во второй строке записаны два числа – координаты собаки. В третьей строке записано число n – число норок на поле. В следующих n строках записаны координаты норок. Все координаты являются целыми числами, по модулю не превышающими 10000, и записываются через пробел. Количество норок не превышает 1000.

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести число – номер норки, если у суслика есть возможность в ней спастись. Если у суслика есть возможность спрятаться в нескольких норках, то выведите ту, которая первая шла во входных данных. Если суслик не может спастись, то выведите в выходной файл «NO» (без кавычек).

begin
  var xg, yg, xd, yd, n, x, y: integer;
  Read(xg, yg, xd, yd, n);
  for var i := 1 to n do
  begin
    Read(x, y);
    if 4 * (Sqr(x - xg) + Sqr(y - yg)) <= Sqr(x - xd) + Sqr(y - yd) then
      begin
        Print(i);
        exit
      end
  end;
  Print('NO')
end.

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

Длина l_AB отрезка AB с координатами (X_A,Y_A) и (X_B,Y_B) находится по формуле $$l_{AB}=\sqrt{\left(X_B-X_A \right)^2+\left(Y_B-Y_A \right)^2}$$

Поскольку важны не длины, а результат их сравнения, можно отказаться от извлечения квадратного корня и сравнивать квадраты длин. В этом случае длину пути суслика нужно брать не удвоенной, а учетверенной (2² = 4).

Введем обозначения: x_g и y_g - координаты суслика (от англ. gopher), x_d и y_d - координаты собаки (dog), а x и y - координаты норки. Тогда суслик спасется, если $$4 \left(\left(x-x_g \right)^2+\left(y-y_g \right)^2\right) \le \left(x-x_d \right)^2+\left(y-y_d \right)^2$$

Обратите внимание на организацию ввода данных. Паскаль при чтении числовых данных не делает разницы между разделителями и ему безразлично, стоит ли за числом пробел или перевод строки. Поэтому можно все данные читать по Read, игнорируя особенности их размещения во входном файле. По крайней мере, тестовая система ACMP “не возражает” против такой организации ввода.

ЗАДАЧА №602 Точки на прямой

(Время: 0,5 сек. Память: 16 Мб Сложность: 32%)

На прямой отмечено N точек. Требуется найти такой отрезок длины L, на котором лежат M из отмеченных точек (M ≥ 2), что величина L/M минимальна. Считается, что точки, совпадающие с одним из концов отрезка, лежат на нем.

Входные данные Входной файл INPUT.TXT содержит количество точек N (2 ≤ N ≤ 10000). На второй строке записаны координаты этих точек X_i - целые числа, разделенные пробелами. При этом |X_i| ≤ 30000 и X_i < X_j при i < j.

Выходные данные В выходной файл OUTPUT.TXT выведите координаты начала и конца найденного отрезка A и B (A < B). Если решений несколько, выведите любое.

begin
  var n, a, b, L, c, d, L1: integer;
  Read(n, c);
  L := 60001;
  loop n - 1 do
  begin
    Read(d);
    L1 := d - c;
    if L1 = 1 then
    begin
      Print(c, d);
      exit
    end;
    if L1 < L then
      (L, a, b) := (L1, c, d);
    c := d
  end;
  Print(a, b)
end.

Этой задаче выставлена сложность 32%. Видимо из-за того, что алгоритм ее решения завуалирован условием. На самом же деле все очень просто. Поскольку координаты точек целые, то расстояние между парой соседних точек не может быть меньше единицы. Это дает соотношение L/M = 0.5. Три точки с расстоянием в единицу дадут соотношение 2/3 > 0.5. Итак, лучшее решение - это отрезок AB из пары соседних точек с длиной, равной единице. Если мы найдем такою пару, последующие точки можно не анализировать. Текущую ситуацию при поиске можно схематически представить следующим образом: ---a----b--------c------d---

Здесь a и b - это “лучшая” пара из просмотренных соседних точек, между которыми минимальное расстояние L. c и d это текущая пара точек с расстоянием L1. Если L1 < L, то запоминаем точки (c,d) в (a,b) соответственно. В начале решения полагаем L= 60001, что превышает максимально возможную длину отрезка. В реализации алгоритма нужно правильно построить “скользящий” отрезок, переприсваивая конец просмотренного отрезка началу нового.

ЗАДАЧА №370 Площадь многоугольника

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Входные данные В первой строке входного файла INPUT.TXT находится число N. В следующих N строках находятся пары чисел (X_i,Y_i) - координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник. (3 ≤ N ≤ 50 000, -20 000 ≤ X_i,Y_i ≤ 20 000)

Выходные данные В выходной файл OUTPUT.TXT выведите одно число - площадь многоугольника. Его следует округлить до ближайшего числа с одной цифрой после запятой.

begin
  var n := ReadInteger;
  var (x, y) := ReadInteger2;
  var (xa, ya) := (x, y);
  (x, y) := (xa, ya);
  var S: int64 := 0;
  loop n - 1 do
  begin
    var (xb, yb) := ReadInteger2;
    S += xa * yb - ya * xb;
    (xa, ya) := (xb, yb);
  end;
  Write(Abs(S + xa * y - ya * x) / 2:0:1)
end.

Самый очевидный для школьника способ нахождения площади многоугольника - разбить его на треугольники, вычислить площадь каждого треугольника и затем найти сумму полученных площадей. Площадь треугольника находится по формуле Герона или определяется через векторное произведение (теми, кто знает, что это такое). Недостаток такого решения состоит в том, что оно переводит задачу в область вещественных чисел, поскольку и формула Герона содержит квадратный корень, и нахождение модуля векторного произведения требует извлечения квадратного корня. Простой и легко программируемый способ нахождения площади многоугольника дает метод Гаусса, известный также, как “формула землемера” или “метод шнурования”.

Одна из возможных записей метода Гаусса имеет следующий вид: $$S=\frac{1}{2}\left|\sum_{i=1}^n{\left( x_iy_{i+1}-y_ix_{i+1}\right)}\right|, \quad x_{n+1}=x_1,\ y_{n+1}=y_1$$

Если положить, что элементом суммы является сторона многоугольника, заданная вершинами А и В с координатами (X_A,Y_A) и (X_B,Y_B) соответственно, можно записать такой элемент в виде X_A * Y_B - Y_A * X_B.

Считываем координаты вершины А и запоминаем их в переменных (x, y) поскольку они еще раз понадобятся для точки n+1. Остальные вершины обрабатываем в цикле как вершину B. Считываем координаты очередной вершины, вычисляем элемент суммы. Затем помещаем координаты вершины B в переменные, отведенные для хранения координат вершины А. После завершения цикла добавляем к сумме последний элемент используя координаты первой вершины, сохраненные в (x, y). И только здесь осуществляем переход к вещественным числам, производя деление на 2. Вывод с одним знаком после запятой во-первых, требуется по условию, а во-вторых целесообразен, поскольку что деление на два в дробной части дает или 0.0, или 0.5.

Для суммы приходится выбирать тип int64. В самом деле, при заданных ограничениях на исходные данные можно получить сумму порядка (20000 - (-20000)) х 2 x 50000 = 4 млрд, что превышает отведенную для типа integer границу 2.1 млрд.