Задача №1780. Атака инопланетян
Олимпиада завершена. Режим дорешивания.
Разбор добавил Александр Чистяков
Первое что нужно понять в этой задаче: пересечение двух описанных равнобедренных прямоугольных треугольников тоже является равнобедренным прямоугольным треугольником. После этого надо научиться правильно находить пересечение двух таких треугольников и прямо во время считывания объединять поступающий треугольник и имеющуюся площадь (изначально удобно добавить фиктивный космический корабль большого размера, покрывающий всю возможную территорию). Опишем механизм нахождения пересечения треугольников T1(x1,y1,s1) и T2(x2,y2,s2): Заметим, что если треугольники вообще пересекаются, то прямой угол нового треугольника имеет координаты x0 = max(x1,x2) и y0 = max(y1,y2). Теперь, зная координаты вершины, нам осталось найти длину катета. Для этого конечно можно рассматривать различные взаимные расположения треугольников, но гораздо удобнее в такой подзадаче использовать бинарный поиск по длине и проверять что точки с координатами (x0+s; y0) и (x0; y0+s) принадлежат каждому из данных треугольников. Условием принадлежности точки (x;y) первому треугольнику является верность выражения |x-x1|+|y-y1| <= s1. Отметим так же тот факт, что при использовании бинарного поиска нам не пришлось проверять наличие области пересечения: если треугольники не пересекаются, то в результате мы получим треугольник с катетом равным 0. Ответом является площадь треугольника оставшегося после пересечения всех считанных: s*s/2
Сдать: для сдачи задач необходимо войти в систему
2917
statement