Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 29484. Вложенный тернарный поиск: футбольные ворота
Темы: Тернарный поиск   

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

Можно считать, что берёза является отрезком прямой и растёт строго перпендикулярно земле.
 
Входные данные
В единственной строке записаны целые числа a, b  — длины палок (\(1 <= a, b <= 10 000\)). Известно, что суммарная длина палок строго меньше высоты берёзы.

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

 

Примеры
Входные данные Выходные данные
1 2 2 4.828427125
Источник: Уральская региональная командная олимпиада по программированию 2011

ID 29479. Дом у дороги
Темы: Вычислительная геометрия    Тернарный поиск   

Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
 
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
 
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
 
Входные данные
Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 104 ).
 
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1)  и (x2, y2) . Координаты заданных точек не превышают по модулю 104. Точки (x1 , y1)  и (x2 , y2)  ни для какой прямой не совпадают.
 
Выходные данные
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 109, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
 
Ответ должен иметь абсолютную или относительную погрешность не более 10−6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10−6.
 
 
Ввод Вывод
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
4040.9996151750674 12003.999615175067

 Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D 

ID 29545. Load Balancing
Темы: Дерево Фенвика    Дерево отрезков, RSQ, RMQ    Структуры данных    Тернарный поиск   

Коровы Фермера Джона стоят в различных точках (x1,y1)…(xn,yn) его поля (1≤N≤100,000, все xi и yi - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.
ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.
ФОРМАТ ВЫВОДА:
Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.
 
Ввод Вывод
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
2