Атака инопланетян

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

Но здесь можно использовать еще более простой принцип, который основан на той идее, что в случае существования треугольника пересечений, мы можем легко определить вершину данного треугольника. Ее координата (x₀,y₀) соответствует максимуму из всех координат заданных кораблей, т.е. координате (max(x_i), max(y_i)), где (x_i,y_i) – координаты носов кораблей. Далее, мы можем вычислять максимально возможный треугольник с прямым углом в координате (x₀,y₀), принадлежащий всем заданным треугольникам. Очевидно, искомый треугольник также будет равносторонним, также можно убедиться в том, что его катет не превышает значения s_i-(x₀-x_i)-(y₀-y_i). Здесь s_i – длины катетов кораблей. Остается найти число s - наименьшее среди данных значений и вывести искомую площадь s²/2, если s неотрицательно, иначе следует вывести 0.

Алгоритмическая реализация данного подхода:

  xx=yy=-inf; ss=inf

  read(n)
  for i=1..n{
    read(x[i], y[i], s[i])
    xx = max(x0, x[i])
    yy = max(y0, y[i])
  }

  for i:=1 to n do
    ss = min(ss, s[i]-(x0-x[i])-(y0-y[i]))
  
  if(ss>0) write(ss*ss/2) else write(0)

[Обсуждение] [Все попытки] [Задача]