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

Во входном файле записано целое число 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 гвоздей, да так, что только шляпки остались. Мало того, они в своих подлых целях вбили все гвозди в вершины выпуклого многоугольника. После этого они... страшно сказать... они натянули ниточку вокруг всех гвоздей, так, что поверхности стало совсем грустно!