Задача A. Пиратская карта ≡

Условие

Капитан Флинт закопал клад с сокровищами на одном из необитаемых островов. Конечно, он составил карту с указанием расположения клада. Для большей сохранности сокровищ он хочет разрезать карту на N кусков и раздать по одному куску каждому члену своей команды. К сожалению, команда Флинта настолько большая, что если капитан начнет резать карту как попало, то быстро устанет. Поэтому он хочет сделать как можно меньше разрезов.

Карта представляет собой прямоугольник размерами A × B, расположенный параллельно осям координат. Левый нижний край имеет координаты (0, 0), правый верхний — (A, B). Требуется написать программу, которая по заданным числам N, A, B выведет количество и коэффициенты прямых a, b, c вида a*x+b*y+c=0, которые разрежут карту ровно на N частей.

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

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

Ограничения

1 ≤ N ≤ 10⁶, 1 ≤ A, B ≤ 10⁹

a_i, b_i, c_i должны быть выведены с абсолютной ошибкой не больше 10⁻⁷

Примеры тестов

1 100 100

0

4 10 10

2
1 -1 0
1 1 -10

Задача B. Новое заклинание ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб выучил новое заклинание. Теперь Хоттабыч может проходить через стены. Хоттабыч знает, что в доме, где живёт его друг Волька, N этажей. На каждом этаже по M квартир, при этом все квартиры одинаковые по размерам. В этом доме номер квартиры состоит из двух чисел — номер этажа и номер квартиры на этаже. На каждом этаже квартиры нумеруются одинаково. То есть для квартиры с номером (i; j) квартиры с номерами (i; j−1) и (i; j+1) будут соответственно соседними слева и справа, а квартиры (i−1; j) и (i+1; j) — снизу и сверху.

Волька живёт в квартире с номером (V_i; V_j), а Волькин друг в квартире (F_i; F_j). Хоттабыч хочет из квартиры Вольки добраться до квартиры его друга, применяя новое заклинание. Находясь в любой квартире, Хоттабыч может перейти в соседнюю квартиру (слева, справа, снизу, сверху), при этом, в зависимости от некоторых особенностей той квартиры, куда пойдёт Хоттабыч, у него будет либо отниматься, либо прибавляться магическая энергия. Для каждой квартиры этого дома Хоттабыч знает на сколько измениться его энергия, при появлении в ней (если число положительное, то столько энергии прибавляется, если же оно отрицательное, то энергия уменьшается на модуль этого числа).

Предоставив вам все необходимые данные, Хоттабыч просит вас написать программу, которая бы рассчитывала минимальные затраты или максимальный прирост магической энергии Хоттабыча при переходе из квартиры (V_i; V_j) в квартиру (F_i; F_j). В случае прироста ответ будет отрицательным. Также Хоттабыч не хочет, чтобы по пути, при переходе через одну стенку, у него отнималось больше 10⁶ единиц энергии.

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

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

• −1 −1, если Хоттабыч не сможет добраться с квартиры Вольки в квартиру его друга
• −2 −2, если по пути Хоттабыч сможет получить бесконечно большой прирост энергии
• Минимальные затраты энергии — в противном случае.

Ограничения

1 ≤ N, M ≤ 650

−1000001 ≤ a(i; j) ≤ 1000000

Примеры тестов

2 2 1 1 2 2
-1 -3
-2 -4
  

6

3 3 3 3 1 1
-1 -1 -1
-1  5  2
-1  4  3
  

-2 -2

3 3 3 3 1 1
      -1 -1000001 -1
-1000001       -1  2
      -1        4  3
  

-1 -1

3 4 2 2 2 3
-20 -20 -20 -20
-20 -20  13 -20
-20 -20 -20 -20
  

-13

Задача C. Исследование Тентуры ≡

Условие

Недавно Плюкианцы решили полностью изучить Тентуру. Для этого они построили очень быстрый пепелац и отправили пацаков в исследовательскую экспедицию. Так как пепелац был очень быстрый, он потреблял много луца, помимо этого, в силу конструктивных особенностей, пепелац не мог летать на большие расстояния, поэтому приходилось приземлятся на каждой планете, которая находилась на траектории полёта. А траектория полёта должна была быть ломаная, отрезки которой, если провести их на карте Тентуры, были параллельны осям координат. При перелёте с одной планеты на другую пепелац потреблял одну единицу луца.

Находясь на одной из исследуемых планет, пацаки заметили, что луца в пепелаце осталось очень мало, они не нашли другого выхода, как попросить вас написать программу, которая, получив карту неисследованной части Тентуры и ещё некоторые данные, рассчитает путь, при котором пацаки исследуют оставшиеся K неисследованных планет и вернутся на Плюк.

Карта неисследованной части Тентуры является прямоугольником ширины W и высоты H. Вся карта разбита на равные квадраты, причём разбиение таково, что в каждом квадрате находится ровно одна планета. Точкой начала отсчёта является левый верхний угол карты. На ней имеются следующие обозначения:

• . — планета известная плюкианцам
• P — планета, которую требуется исследовать
• # — планета, рельеф которой не позволяёт приземляться на неё пепелацу
• S — планета, на которой сейчас находится исследовательский пепелац
• F — планета Плюк

На планетах Тентуры есть E гравицапп. Гравицаппа позволяет перемещаться по Тентуре с огромной скоростью без использования луца. Список планет, где находятся гравицаппы и куда можно попасть при её использовании, прилагается к карте.

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

В первой строке входного файла содержатся числа H W K

Далее следуют H строк по W символов в каждой — карта неисследованной части тентуры

В H+2-ой строке содержится число E

Далее следуют E строк по четыре числа в каждой: первые два задают планету, на которой есть гравицаппа, вторые два — планету, где оказывается пепелац после её использования (сначала указывается координата по вертикальной оси, затем по горизонтальной). На одной планете может быть несколько гравицапп.

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

• −1 — в случае, если пацаки не смогут вернуться на Плюк, изучив все планеты
• Минимальное количество единиц луца, которое потребуется для исследования всех планет Тентуры и возвращения на Плюк — в противном случае

Ограничения

1 ≤ W, H ≤ 150000

2 ≤ W × H ≤ 150000

0 ≤ K ≤ 10

0 ≤ E ≤ 10⁴

Примеры тестов

3 4 3
.SP.
.##.
FP#P
2
3 1 1 4
2 4 1 3

11

Задача D. Привлекательный треугольник ≡

Условие

Назовём отрезок симпатичным, если он параллелен одной из координатных осей. Если в треугольнике хотя бы одна из сторон — симпатичный отрезок, то треугольник также называется симпатичным. Симпатичный треугольник является привлекательным, когда проекции всех его вершин на все прямые, содержащие симпатичные стороны, попадают на эти стороны.

Каждый привлекательный треугольник имеет определённую красивость. Красивость привлекательного треугольника определяется количеством единичных квадратиков координатной сетки, которые полностью попали внутрь треугольника. Требуется написать программу, которая по заданным трём точкам определит:

1. можно ли по ним построить треугольник (должно выполняться неравенство треугольника),
2. если можно, то является ли он привлекательным,
3. если треугольник привлекательный, то какова его красивость.

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

Во входном файле содержатся целые числа x₁ y₁ x₂ y₂ x₃ y₃, по одному числу в строке. Входной файл также заканчивается переводом строки.

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

• −1, если треугольник построить невозможно или он не является привлекательным;
• красивость треугольника — в противном случае.

Ограничения

Примеры тестов

-1
-3
5
-1
-1
5

18

-3
-4
-7
-7
4
-4

-1

-3
-3
-1
-7
4
-4

-1