0247. Десант

Input file name:	attack.in
Output file name:	attack.out
Time limit:	2 s
Memory limit:	256 megabytes

Вероломный генерал терран Алекс Стуков решил захватить город протоссов Талдарим. Вам же требуется составить план нападения.

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

Введём в городе декартову прямоугольную систему координат. Тогда место высадки захватчиков и положения пилонов города можно обозначить парой целых чисел (x, y) – координатами в этой системе. Расстояние между точками (x₁, y₁) и (x₂, y₂) определяется как сумма модулей разности соответствующих координат (|x₁ - x₂| + |y₁ - y₂|).

Захват города происходит следующим образом. Пусть n – количество работающих пилонов, тогда n захватчиков высаживаются в некоторой точке (обозначим её (x, y)). Каждый из них идёт к одному пилону по кратчайшему пути. Никакие два захватчика не идут к одному пилону. Опасностью операции называется суммарное расстояние от точки высадки до каждого из пилонов. Чтобы операция прошла удачно, требуется найти точку высадки с минимальной опасностью. Если таких точек несколько требуется вывести ту, у которой координата x минимальна. Если и таких точек несколько, то требуется вывести ту, у которой координата y минимальна.

Изначально нет работающих пилонов.

Формат входного файла

В первой строке входного файла находится число q (1 ≤ q ≤ 100000) – количество изменений в системе пилонов города. Следующие q строк содержат по три целых числа t, x, y (-10⁹ ≤ x, y ≤ 10⁹) – тип изменения и координаты точки нового пилона. Если t равно 1, то это значит, что пилон с координатами в точке (x, y) введен в эксплуатацию. Если t равно -1, то это значит, что пилон с коодинатами в точке (x, y) вышел из строя. Гарантируется, что перед тем, как пилон вышел из строя, он работал. Никакие два работающих пилона не будут находиться в одной точке. Гарантируется, что после каждого действия существует хотя бы один рабочий пилон.

Формат выходного файла

В выходной файл выведите q строчек. В i–ой строчке выходного файла выведите два числа – координаты оптимальной точки высадки, после i–ого изменения в системе пилонов города.

Пример:

attack.in	attack.out
3 1 1 1 1 1 2 -1 1 1	1 1 1 1 1 2
10 1 -6 3 1 10 -6 -1 10 -6 1 -10 4 1 4 -10 1 -2 7 1 -9 -1 1 -8 -3 1 2 9 1 -5 -7	-6 3 -6 -6 -6 3 -10 3 -6 3 -6 3 -6 3 -8 -1 -6 3 -6 -1

Source: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Author: Никита Иоффе

Discuss       Submit a solution



Printable version