Задача B. Юный поджигатель
Условие
На клеточном поле введена система координат так,
что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
- Спички длины 1 выкладывались по сторонам клеток.
- Спички длины sqrt(2) выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке,
имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью).
Спичка может гореть в нескольких местах (например, когда она загорается с двух концов;
или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается
по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Формат входного файла
Во входном файле записано сначала число
N - количество спичек.
Затем идет
N пятерок чисел вида
X1,
Y1,
X2,
Y2,
T, задающих координаты
концов спички и время ее сгорания при условии, что она будет подожжена с одного конца
(гарантируется, что каждая спичка имеет длину 1 или sqrt(2), все спички образуют связную фигуру,
и положение никаких двух спичек не совпадает).
Формат выходного файла
Выведите минимальное время сгорания фигуры.
Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки.
Если решений несколько, выведите любое из них.
Ограничения
1 ≤
N ≤ 40
Все координаты — целые числа, по модулю не превышающие 200,
время сгорания — натуральное число, не превышающее 10
7.
Примеры тестов
| № |
Входной файл (f.in) |
Выходной файл (f.out) |
|---|
| 1 |
1
0 0 1 1 1
|
1.00
|
| 2 |
5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1
|
3.25
|
| 3 |
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
|
35.00
|
| 4 |
16
0 0 0 1 1 -2 -1 -3 -1 1 -2 -1 -1 0 1 -2 -1 -1 -2 1
-1 0 0 0 1 0 3 1 3 1 1 3 2 2 1 2 2 2 1 1
2 1 1 0 1 2 0 1 1 1 2 0 1 0 1 2 1 1 1 1
0 0 1 0 1 0 1 -1 1 1 -1 1 -1 2 1 0 3 -1 2 1
|
4.50
|
Задача C. Последовательность
Условие
Дана последовательность целых чисел a1, a2, ..., an, каждое из которых
по модулю не превосходит 10000. Эта последовательность записана на бумажной ленте, которая свернута в кольцо.
Разрежем эту кольцо в некоторой точке между числами, получим полоску с записанной
на ней последовательностью следующего вида:
aj, aj+1,..., an, a1, a2, ..., aj − 1.
Назовем точку разреза хорошей, если все частичные суммы полученной последовательности строго положительны:
aj > 0,
aj + aj+1 > 0,
....
aj + aj+1 + ... + an > 0,
aj + aj+1 + ... + an + a1 > 0,
...
aj + aj+1 + ... + an + a1 + a2 + ... + aj − 2 > 0,
aj + aj+1 + ... + an + a1 + a2 + ... + aj − 2 + aj − 1 > 0.
Вам требуется вычислить число хороших точек разреза.
Формат входного файла
Первая строка входного файла содержит число n, а во второй строке заданы числа
a1,
a2, ...,
an.
Формат выходного файла
Выведите в выходной файл число искомых хороших точек разреза.
Ограничения
1 ≤
n ≤ 100000
Примеры тестов
| № |
Входной файл (seq.in) |
Выходной файл (seq.out) |
|---|
| 1 |
5
0 1 -2 10 3
|
2
|
Задача D. Максимальный квадрат
Условие
На плоскости задан прямоугольник размером
W × H, и
N отмеченных точек внутри него.
Требуется найти квадрат максимального размера:
- со сторонами, параллельными сторонам прямоугольника;
- не содержащий отмеченных точек строго внутри себя
(но, возможно, содержащий отмеченные точки на границе);
- лежащий внутри прямоугольника.
Формат входного файла
Первая строка входного файла содержит числа
N — количество отмеченных точек,
W — ширину прямоугольника и
H — высоту прямоугольника.
Следующие
N строк содержат координаты отмеченных точек
Xi, Yi
(целые числа,
0 ≤ Xi ≤ W,
0 ≤ Yi ≤ H).
Система координат введена так, что вершины прямоугольника имеют координаты
(0, 0), (
W, 0), (0,
H), (
W,
H).
Формат выходного файла
Выведите в выходной файл одно число — длину стороны максимального искомого квадрата.
Ограничения
1 ≤ N ≤ 30000
0 ≤ W, H ≤ 1000000.
Примеры тестов
| № |
Входной файл (square.in) |
Выходной файл (square.out) |
|---|
| 1 |
7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7
|
4
|
| 2 |
1 10 10
5 5
|
5
|
