---> 5 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан выпуклый многоугольник, необходимо определить минимальную величину Dmin*Dmax, где Dmin (Dmax) - минимальное и максимальное расстояние от начала координат по всевозможным лучам.

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

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

Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: dmin и dmax. Степенью точки относительно данного многоугольника назовем минимум величины dmin×dmax по всем таким лучам.

Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!

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

Будем считать, что наблюдательный центр находится в точке (0, 0). На вход программы поступает описание полигона.

В первой строке вводится число n – количество вершин полигона ( 3$ le$n$ le$100). Следующие n строк содержат по два вещественных числа – координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают 1000 по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

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

Выведите одно число – степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на 10-4.

includegraphics{pics/polygon.1}
Примеры
Входные данные
3
1.0 2.0
3.0 2.0
0.5 3.25
Выходные данные
7.0000000000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано кубическое уравнение $ax^3 + bx^2 + cx + d = 0 \;(a \ne 0)$. Известно, что у этого уравнения ровно один корень. Требуется его найти.

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

Во входных данных через пробел записаны четыре целых числа: $-1000 \le a,\,b,\,c,\,d \le 1000$.

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

Выведите единственный корень уравнения с точностью не менее 4 знаков после десятичной точки.

Примеры
Входные данные
1 -3 3 -1
Выходные данные
0.999999598818135
Входные данные
-1 -6 -12 -7
Выходные данные
-0.999999999990564

Найдите корень уравнения sin(x)=a на отрезке [ - π / 2, π / 2].

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

Вводится одно вещественное число а, по модулю не превосходящее 1.

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

Выведите корень уравнения с точностью не менее 5 знаков после запятой.

Примеры
Входные данные
0.5
Выходные данные
0.523598775598
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Найдите такое число $x$, что $x^2 + \sqrt{x} = C$, с точностью не менее $6$ знаков после точки.

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

В единственной строке содержится вещественное число $1.0 \le C \le 10^{10}$.

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

Выведите одно число — искомый $x$.

Примеры
Входные данные
2.0000000000
Выходные данные
1.000000000
Входные данные
18.0000000000
Выходные данные
4.000000000
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Силовое поле
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Империя обнаружила мятежников на ледяной планете Хот! По сведениям разведки все командование Альянса Повстанцев сейчас скрывается на базе «Эхо», спрятанной в горах на севере этой суровой планеты.

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

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

На планете введена система координат, устроенная таким образом, что все станции-ре-транс-ля-торы находятся в точках с целыми координатами, не превосходящими C по модулю.

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

С повстанцами надо расправиться как можно скорее: у вас есть время не более чем на 105 запусков этого зонда. Восстановите по полученной от него информации точные координаты станций-ретрансляторов, чтобы мы могли начать наступление, и Империя вас не забудет!

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

Это интерактивная задача.

При запуске решения на вход подаются два целых числа N (3 ≤ N ≤ 1 000) и C (5 ≤ C ≤ 1 000 000) — количество станций и ограничение на абсолютную величину их координат.

На каждый запуск зонда-разведчика вводится полученная им информация — два целых числа l и r, разделенных пробелом, — количество станций-ретрансляторов слева и справа от траектории его движения соответственно.

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

Для запуска зонда выведите строку «? x1 y1 x2 y2», где (x1, y1) и (x2, y2) — две точки с целочисленными координатами, лежащие на прямой, по которой должен лететь зонд. Зонд будет лететь в направлении от первой точки ко второй. Точки не должны совпадать. Координаты точек не должны превосходить 5C по модулю.

Как только вы найдете ответ, выведите строку «Ready!», и в следующих N строках выведите координаты станций в любом порядке. После этого ваша программа должна завершиться.

Примеры

Входные данные
4 5
0 4
0 3
0 3
0 2
1 1
3 1
3 0
3 0
Выходные данные
? -1 3 1 3
? -1 2 1 2
? -1 1 0 2
? -1 0 0 2
? 0 0 0 2
? 1 0 1 2
? 2 0 2 2
? 3 0 1 2
Ready!
0 -1
2 1
0 2
-1 0

Примечание

В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

Программа не должна делать более 105 запросов запуска зонда. При превышении этого количества, тест будет не пройден с вердиктом «Wrong Answer».

Тесты к этой задаче состоят из четырех групп.

  • Тест 1. Тест из условия, оцениваемый в ноль баллов.
  • Тесты 2–11. В тестах этой группы N = 3, C ≤ 10. Эта группа оценивается в 30 баллов.
  • Тесты 12–24. В тестах этой группы N ≤ 50, C ≤ 100. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
  • В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп.

Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

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

Чтобы протестировать свое решение, наберите в командной строке "test.bat <solution> <test>" или "bash test.sh <solution> <test>", где <solution> — исполняемый файл вашего решения, а <test> — файл, описывающий тест в следующем формате. В первой строке должны находиться два целых числа N и C, разделенных пробелом. В последующих N строках должны следовать координаты N станций-ретрансляторов в порядке обхода против часовой стрелки.

Утилита сообщит вам вердикт, который получило бы решение на этом тесте в тестирующей системе, и запишет в файл <test>.log полный протокол взаимодействия вашей программы и тестирующей.

Примеры
Входные данные
4 5
-1 0
0 -1
2 1
0 2
Выходные данные
28

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест