Страница: 1 Отображать по:
#574
Выпуклая оболочка
  
Источники: [ Командные олимпиады, ВКОШП, 2007, Задача C ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
На плоскости заданы углы (фигура, образованная лучами, исходящими из одной точки). Требуется найти "выпуклую оболочку", которая также ограничена двумя лучами.

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек \(X\), называется выпуклой оболочкой множества \(X\).

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

Входные данные

В первой строке вводится число \(n\) - количество углов (1 <= \(n\) <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают \(10^4\) по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

Выходные данные

Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить \(10^5\) по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа. На первой строке выведите \(L\) - количество объектов в ответе. Следующие \(L\) строк должны содержать описание объектов. Объекты описываются следующим образом:

*Отрезок: "segment \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)) - концы отрезка, отрезок считается направленным от (\(x_1\), \(y_1\)) к (\(x_2\), \(y_2\)).
*Луч, направленный от начала: "outray \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) - начало луча, а (\(x_2\), \(y_2\)) - произвольная точка на луче, отличная от начала.
*Луч, направленный к началу: "inray \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_2\), \(y_2\)) - начало луча, а (\(x_1\), \(y_1\)) - произвольная точка на луче, отличная от начала.
*Прямая: "line \(x_1\) \(y_1\) \(x_2\) \(y_2\)", где (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)) - две точки на прямой, причем при движении вдоль прямой в ее направлении точка (\(x_1\), \(y_1\)) следует ранее точки (\(x_2\), \(y_2\)).
*Если выпуклой оболочкой является вся плоскость, то выведите \(L\) = 0.

Примеры
Входные данные
2
3 1 4 1 4 4
2 2 4 3 3 4
Выходные данные
3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5
Входные данные
2
0 0 1 0 0 1
0 0 -1 0 0 1
Выходные данные
1
line 0 0 -1 0
Входные данные
2
0 0 1 0 0 1
0 0 -1 0 0 -1
Выходные данные
0
#578
Жребий Крижановского
  
Источники: [ Командные олимпиады, ВКОШП, 2007, Задача G ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

Петя с друзьями при игре просто называют по очереди загаданные ими числа, а потом определяют, кто выиграл, и подсчитывают баллы. Однако при таком формате игры в принципе можно сжульничать, не загадывая число заранее, а, уже зная числа, названные предыдущими игроками, выбрать себе оптимальное "загаданное" число. Этим и пользуется Петя. Он называет число последним и старается выбрать число так, чтобы максимизировать свой выигрыш.

Идет последний тур игры. Известны очки всех игроков перед этим туром и названные игроками числа. Выясните, какое число следует назвать Пете, чтобы по результатам игры у как можно большего числа игроков количество баллов было меньше, чем у него. Если таких чисел несколько, то Петя хочет назвать минимальное возможное.

Входные данные

В первой строке вводится число \(n\) - количество игроков (2 <= \(n\) <= 100). Вторая строка содержит \(n\) чисел - баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). В третьей строке задано (\(n\)-1) число - числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Выходные данные

Выведите число, которое следует назвать Пете.

Пояснения

Во втором примере Петя не может выиграть в последнем туре. Однако, назвав число 2, Петя не позволяет выиграть первому игроку, и ,тем самым, остается вторым по итогам всей игры. У четырех игроков баллы меньше, чем у Пети.

Примеры
Входные данные
6
0 0 0 0 0 0
2 3 4 5 6
Выходные данные
1
Входные данные
6
8 3 12 5 0 9
2 1 3 1 4
Выходные данные
2
#581
Гражданская оборона
  
Источники: [ Командные олимпиады, ВКОШП, 2007, Задача J ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.

Входные данные

В первой строке вводится число n - количество селений (1 <= \(n\) <= 100000). Вторая строка содержит n различных целых чисел, \(i\)-е из этих чисел задает расстояние от начала дороги до \(i\)-го селения. В третьей строке входных данных задается число \(m\) - количество бомбоубежищ (1 <= \(m\) <= 100000). Четвертая строка содержит \(m\) различных целых чисел, \(i\)-е из этих чисел задает расстояние от начала дороги до \(i\)-го бомбоубежища. Все расстояния положительны и не превышают \(10^9\). Селение и убежище могут располагаться в одной точке.

Выходные данные

Выведите \(n\) чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до \(m\) в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
4
1 2 6 10
2
7 3
Выходные данные
2 2 1 1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест