На территории строительства растут два дерева. Согласно плану работ, оба дерева попадают внутрь будущей цветочной клумбы, имеющей форму круга. Нужно огородить эти деревья треугольным забором так, чтобы ограждение содержалось внутри будущей клумбы.
Деревья на плане изображаются кругами, которые могут пересекаться друг с другом или даже быть вложены один в другой (деревья могли срастись из-за локальных загрязнений окружающей среды, неизбежных при строительстве). Они лежат внутри окружности, соответствующей клумбе, но могут касаться её.
Напишите программу, которая по введенной информации о клумбе и деревьях определит, возможно ли построить треугольный забор, не выходящий за пределы клумбы (при этом его вершины могут лежать на границе клумбы) и содержащий оба дерева внутри (касание забора и деревьев также разрешается).
Вводится информация о трех окружностях: каждая задается координатами центра и радиусом. Все числа целые, не превосходящие по модулю 1000, радиус – натуральное число. Клумбе соответствует первая окружность, вторая и третья окружности лежат внутри первой и соответствуют деревьям.
Если деревья невозможно оградить забором, не выходящим за границы клумбы, выведите impossible. Иначе в первую строку запишите possible, а в следующие – координаты вершин искомого треугольника. Если ответов несколько, выведите любой.
0 0 1000 0 0 500 0 0 500
possible -468.09507906626652000000 -883.67810709213904000000 -531.24014997680422000000 847.22128340394170000000 999.33522904307131000000 36.45682368819722500000
В волшебном лесу растут N деревьев. На плане леса они изображены точками (диаметром деревьев можно пренебречь). Территорией леса считается наименьший по площади выпуклый многоугольник (возможно, вырожденный), содержащий в себе все деревья.
Отважный путешественник и писатель Ручкин однажды решился на отчаянный поступок — он совершил путешествие в этот лес. После этого он описал свое путешествие в книге. В частности, в книге описаны все деревья леса в том порядке, в каком они встречались Ручкину (каждое дерево описано ровно один раз).
Художник Кистин решил нарисовать иллюстрацию для этой книги. Для этого он приехал и остановился в деревне недалеко от волшебного леса. Теперь он хочет выбрать точку, с которой он будет рисовать иллюстрацию. Кистин очень боится заходить в волшебный лес, поэтому хочет найти точку для рисования обязательно за пределами леса (в том числе, она не может находиться на границе леса).
Он решил нарисовать весь лес: он хочет взять длинный-длинный холст, и зарисовать весь лес справа налево, от самой правой точки леса до самой левой. При этом деревья леса должны на картине идти справа налево ровно в том же порядке, в котором они описаны в книге. Естественно, никакое дерево не должно быть заслонено другим деревом (т.е. на отрезке между Кистиным и деревом не может быть других деревьев).
Помогите ему: напишите программу, которая по координатам деревьев волшебного леса в том порядке, в каком они описаны у Ручкина, поможет Кистину выбрать точку, из которой деревья видны в требуемом порядке.
Задано число N — количество деревьев в лесу (1 ≤ N ≤ 100000). Далее перечислено N пар чисел, задающих координаты деревьев в том порядке, в каком они описаны в книге Ручкина. Все координаты – целые числа, не превосходящие по абсолютной величине 105. Гарантируется, что никакие два дерева не растут в одной точке.
Если подобрать точку для Кистина возможно, выведите сообщение Possible, а в следующей строке — два вещественных числа: координаты точки. Координаты выведенной точки не должны превышать 1015 по абсолютной величине. Если подобрать точку с указанными ограничениями не удастся, выведите сообщение Impossible.
При проверке ответа для случая Possible он будет считаться верным, если на расстоянии менее 10–5 от выведенной точки будет существовать точка, удовлетворяющая условию.
Примеры
| Входные данные | Выходные данные |
| 3 0 0 1 2 2 1 | Possible 1 4 |
| 3 1 0 2 0 3 0 | Possible 1 1 |
| 3 1 0 3 0 2 0 | Impossible |
| 4 0 0 2 3 4 2 3 1 | Impossible |
| 4 0 0 4 0 2 2 4 4 | Possible -2 2 |
Однажды майор Пронин затеял в квартире ремонт. В одной из стен на кухне по плану потребовалось последовательно проделать (N–1) прямоугольных вентиляционных отверстий с горизонтальными и вертикальными сторонами (0 < N < 101). Если оказывалось, что очередное отверстие пересекается с уже проделанными, то майор вырезал только нетронутую часть соответствующего прямоугольника.
Следующая стадия после ремонта – это поклейка обоев. В магазине напротив майор может заказать не более (2N–1)2 прямоугольных кусков обоев любых размеров c ненулевой площадью. Он хочет обклеить стену кусками обоев так, чтобы:
1. Вентиляционные отверстия не были заклеены даже частично.
2. Никакие два куска не пересекались (касаться сторонами они при этом могут).
На стене не осталось бы непокрытой области.
Рассмотрим декартову систему координат, оси которой параллельны сторонам отверстий и стены.
Сначала вводится число N (0 < N < 101), далее – описание N прямоугольников. Первый прямоугольник описывает положение стены в нашей системе координат, остальные (N–1) ― положения отверстий в порядке их появления. Стороны всех прямоугольников параллельны осям координат. Каждый прямоугольник задаётся координатами своих левого нижнего и правого верхнего углов: x1, y1, x2, y2. Координаты — целые числа, не превосходящие по модулю 31000, x1 < x2, y1 < y2.
Прямоугольники, обозначающие положение отверстий, могут пересекаться и касаться, поскольку это могло быть необходимо в ходе ремонта. Разумеется, все вентиляционные отверстия находятся в стене, то есть не выходят за границы первого прямоугольника.
Вначале выведите количество кусков обоев K, которое нужно заказать в магазине (K должно быть не больше (2N–1)2). Далее выведите схему поклейки: K прямоугольников, обозначающих места расположения заказанных кусков. Для каждого прямоугольника нужно вывести координаты его левого нижнего и правого верхнего углов. Все координаты должны быть целыми числами. Гарантируется, что решение существует.
Если возможных способов несколько, выведите любой.
2 -1 -1 2 2 0 0 1 1
5 -1 -1 2 0 -1 0 0 2 0 1 1 2 1 0 2 1 1 1 2 2
Две страны Байтландия и Флатландия решили объединить свои усилия в исследованиях в области физики высоких энергий и построили \(n\) адронных коллайдеров. Каждый коллайдер имеет форму кольца и находится под землей. При этом можно считать, что толщина каждого из коллайдеров пренебрежимо мала — их можно считать окружностями.
Как известно, адронные коллайдеры — устройства сложные и требующие постоянного внимания. Ни одна из стран не хочет брать на себя обслуживание всех коллайдеров, поэтому было решено поделить обслуживание коллайдеров между странами. Для того чтобы все было честно, было решено, что каждая из стран будет обслуживать ровно половину каждого из коллайдеров. Границу зон ответственности было решено провести в виде окружности. Таким образом, необходимо найти окружность, которая разбивает каждый из коллайдеров на две равные по длине части (то есть пересекает каждый из них в двух диаметрально противоположных точках).
Требуется написать программу, которая по описанию построенных коллайдеров найдет окружность, удовлетворяющую указанным требованиям.
Первая строка входного файла содержит целое число \(n\) (\(1 \le n \le 3\)). Каждая из последующих \(n\) строк содержит описание одного из коллайдеров. Описание коллайдера состоит из трех целых чисел: \(x\), \(y\), \(r\) — координат центра коллайдера и его радиуса (\(|x|\), \(|y|\) \(\le 1000\), \(1\) \(\le r\) \(\le 1000\)). Коллайдеры не имеют общих точек, не лежат один внутри другого, а их центры (если \(n = 3\)) не находятся на одной прямой.
В первой строке выходного файла описание искомой границы: координаты центра окружности и радиус. Выводите как можно больше знаков после десятичной точки. При проверке правильности ответа, погрешности, не превышающие \(10^{-5}\), будут игнорироваться.
Координаты центра и радиус окружности не должны превосходить \(10^7\) по абсолютной величине. Гарантируется, что существует решение, удовлетворяющее указанному ограничению.
2 2 0 1 -2 0 1
0.0 0.0 2.23606797749979
3 0 10 1 0 0 2 10 10 3
5.4 4.85 7.52877812131557
Вы уже знаете, сколько нефти добывается в Ханты-Мансийском автономном округе. Другой хозяйственной отраслью Югры является оленеводство. Нередко можно увидеть, как на нефтяной площадке, окружённой изгородью, работают нефтяники, а вокруг изгороди пасутся олени.
Оленевод Ванхо привязал своего оленя Ахтамака к изгороди нефтяной площадки, имеющей форму выпуклого многоугольника. Олень был привязан на длинной верёвке, чтобы он не убежал и при этом мог пастись. Вокруг нефтяной вышки растёт такой вкусный ягель, что олень тут же принялся его щипать.
Напишите программу, вычисляющую площадь участка вне изгороди, ягель на котором будет доступен оленю. Форма изгороди, точка привязывания и длина верёвки задаются во входном файле.
В первой строке входного файла записано целое число \(n\) — количество углов изгороди (\(3\le n\le100\)). В последующих \(n\) строках записаны координаты углов изгороди в порядке обхода по часовой стрелке. В последней строке записаны три числа — координаты точки привязывания оленя к изгороди и длина верёвки. Все координаты целые и не превосходят по модулю \(10^4\). Длина верёвки — целое положительное число, не превосходящее \(10^4\). Числа в каждой строке разделены пробелами. Гарантируется, что изгородь представляет собой строго выпуклый многоугольник и точка привязывания оленя лежит на его границе.
В выходной файл выведите значение площади с точностью не менее \(10^{-3}\).
Система оценивания
Решения, корректно работающие на тестах из примеров, а также в случае, если длина верёвки не превосходит половины периметра изгороди и изгородь представляет собой прямоугольник со сторонами, параллельными осям координат, будут оцениваться из 30 баллов.
Решения, корректно работающие на тестах из примеров, а также в случае, если длина верёвки не превосходит половины периметра изгороди, будут оцениваться из 60 баллов.
4 -5 -5 -5 5 5 5 5 -5 5 0 4
25.1327412287
4 0 0 0 2 4 2 4 0 2 0 4
31.4159265359