Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия
---> 55 задач <---
Страница: << 5 6 7 8 9 10 11 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Для того, чтобы окончательно подавить силы восстания, необходимо в ходе стремительной атаки уничтожить эту базу и скрывающихся на ней мятежников. К сожалению, укрытие хорошо укреплено: в частности, его защищает мощное силовое поле, препятствующее бомбардировкам с орбиты. Силовое поле имеет форму выпуклого многоугольника с вершинами в 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 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй группы.

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

Примеры
Входные данные
4 5
-1 0
0 -1
2 1
0 2
Выходные данные
28
ограничение по времени на тест
2.5 second;
ограничение по памяти на тест
512 megabytes

На улице уже неделю лил беспросветный дождь, а Игорь все сидел дома и играл в свои любимые игрушки. Но играть так долго в одно и то же ему быстро надоело, и он пошел к родителям выпрашивать новые. Родители быстро сдались, поэтому на следующий день вся семья собралась, и они поехали в магазин игрушек.

При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.

Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.

Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.

Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.

Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.

Формат входного файла

В первой строке содержится натуральное число \(N\) (1 ≤ \(N\) ≤ 100 000) - количество игрушек. Далее следуют описания \(N\) выпуклых многоугольников в следующем формате: сначала идет натуральное число \(k_m\) (3 ≤ \(k_m\) ≤ 300 000) - количество вершин в \(m\)-м многоугольнике, затем идут \(k_m\) строк, в которых записаны пары целых чисел xm,s, ym,s, по модулю не превосходящих \(10^9\) - координаты вершин \(m\)-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что ym,s >= 0, а также для всех игрушек существует вершина \(v_m\), у которой ym,\(v_m\) = 0). Сумма всех \(k_m\) (обозначим ее за \(S\)) не превосходит 300 000.

В следующей строке записано натуральное число \(Q\) (1 ≤ \(Q\) ≤ 500 000) - число вариантов. Следующие \(Q\) строк содержат пары натуральных чисел \(i_t\), \(j_t\) (1 ≤ \(i_t\) < \(j_t\) ≤ \(N\)) - номера сдвигаемых игрушек в очередном варианте.

Формат выходного файла

Выведите \(Q\) строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более \(10^{-9}\).

Комментарий

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

Система оценивания

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

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–20. В тестах этой группы \(k_m\) ≤ 100, \(Q\) ≤ 1 000, \(S\) ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 21–40. В тестах этой группы \(k_m\) ≤ 300, \(Q\) ≤ 50 000, \(S\) ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.

3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
2
5
0 0
4 2
6 6
3 8
-2 4
5
0 0
2 0
8 4
5 11
3 12
1
1 2
Выходные данные
14.5000000000
Входные данные
2
3
0 0
0 3
-1 1
3
0 0
1 0
-20 20
1
1 2
Выходные данные
21.0000000000
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Даны несколько ломанных (кусочно-линейных функций, определённых на отрезке \([a, b]\)). Требуется определить, верно ли, что для каждой пары таких функций одна из функций больше либо равна, чем другая во всех точках отрезка \([a, b]\)

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

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

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от \(1\) до \(N\), где горная цепь с номером i представляет собой ломаную на плоскости из \(l_i\) звеньев с вершинами в точках (\(x_i\),\(j\) , \(y_i\),\(j\) ), причем для любых \(i\), \(j\) выполнено \(x_{i,j} < x_{i,j+1}\).

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа \(A\) и \(B\), что для любого номера \(i\) горной цепи выполнено \(x_{i,0} = A, x_{i,l_i} = B\).

Отметим, что из определения горной цепи следует, что для любого значения абсциссы \(A \le x \le B\) на ломаной с номером \(i\) существует единственная точка (\(x\), \(y_i\)(\(x\))) с этим значением абсциссы, принадлежащая этой ломаной. Будем говорить, что горная цепь \(i\) находится строго выше горной цепи \(j\) в точке \(x\), если выполнено строгое неравенство \(y_i(x) > y_j (x)\).

Естественно считать, что цепь под номером \(i\) пересекается с цепью под номером \(j\), если существуют такие два значения абсциссы \(x_1\), \(x_2\), что цепь \(i\) находится строго выше цепи \(j\) в точке \(x_1\), но при этом цепь \(j\) находится строго выше цепи \(i\) в точке \(x_2\), то есть выполнены неравенства \(y_i\)(\(x_1\)) > \(y_j\) (\(x_1\)) и \(y_j\) (\(x_2\)) > \(y_i\)(\(x_2\)). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

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

В первой строке входных данных через пробел идут два целых числа: \(A\) и \(B\) (\(−10^9 \le A < B \le 10^9\) ).

Во второй строке входных данных находится единственное число \(N\) — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (\(1 \le N \le 100 000\)).

Далее следуют описания N горных цепей. В первой строке i-го описания содержится число \(l_i \ge 1\) — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следующих \(l_i\) + 1 строках описания содержатся два целых числа — координаты (\(x_{i, j} , y_{i,j}\) ) вершин ломаной (\(0 \le j \le l_i\)). Суммарное число звеньев всех ломаных не превосходит 200 000.

Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого \(i\) выполнено \(x_{i,0} = A, x_{i,l_i} = B\).

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

Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересекаются, в единственной строке выходных данных выведите слово «Yes» (без кавычек).

Иначе выведите в первой строке слово «No» (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Замечание

Напоминаем, что абсциссой точки называется её \(x\)-координата, а ординатой — её \(y\)-координата.

В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются.

Во втором примере в точке \(x_1\) = 1 одна ломаная выше другой, а в точке \(x_2\) = 3 — наоборот, то есть горные цепи пересекаются.

Система оценки

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.

Примеры
Входные данные
-3 3
2
1
-3 2
3 1
2
-3 2
0 4
3 2
Выходные данные
Yes
Входные данные
0 4
2
3
0 3
1 3
3 1
4 1
1
0 2
4 2
Выходные данные
No
1 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

В заповеднике живут q тигров. Чтобы следить за положением тигров на территории заповедника, используются ошейники с радиомаяком. Ошейник у каждого тигра имеет радиомаяк с уникальным сигналом. Система обнаружения настраивается на приём сигнала радиомаяка от i-го тигра последовательно для i от 1 до q.

Для приёма сигнала на территории заповедника установлено n приёмников в точках с координатами (x1, y1), ..., (xn, yn). Система обнаружения позволяет сотруднику заповедника за один запрос выбрать любые m (3 ≤ m ≤ n) приёмников. Выбранные приёмники должны являться вершинами выпуклого многоугольника. Система определяет, находится ли радиомаяк i-го тигра внутри этого многоугольника.

Сотрудник заповедника должен локализовать положение каждого тигра. Положение i-го тигра считается локализованным, если удалось определить такое множество приёмников, являющихся вершинами выпуклого многоугольника, что внутри этого многоугольника находится тигр, но нет других приёмников.

Для того, чтобы локализовать положение каждого из тигров, сотруднику разрешается сделать не более k запросов.

После того как положение i-го тигра локализовано, система автоматически переходит к приёму сигналов от следующего тигра, пока положение всех q тигров не будет локализовано.

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

Требуется написать программу, которая взаимодействует с программой жюри и локализует положение каждого тигра.

Протокол взаимодействия

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

Сначала на вход подаётся информация об установленных в заповеднике приёмниках и количестве тигров.

Первая строка входных данных содержит целое число n — количество приёмников (3 ≤ n ≤ 5 000). Последующие n строк описывают координаты приёмников, j-я из этих строк содержит два целых числа xj и yj — координаты j-го приёмника ( - 109 ≤ xj, yj ≤ 109). Следующая строка содержит число целое число q — количество тигров (1 ≤ q ≤ 2000).

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

Для каждого теста зафиксировано число k — максимальное количество запросов к системе обнаружения для локализации положения одного тигра. Гарантируется, что k запросов достаточно, чтобы решить задачу для соответствующих данных. Это число не сообщается программе-решению, но ограничения на него в различных подзадачах приведены в таблице системы оценивания. Если программа-решение делает более k запросов для определения местоположения одного из тигров, на этом тесте она получает в качестве результата тестирования «Неверный ответ».

Запрос к системе обнаружения начинается с символа «?», за которым следует целое число m — количество выбранных в запросе приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n).

В ответ программа получает строку «Yes», если тигр находится внутри многоугольника, образованного приёмниками с номерами p1, ..., pm, и строку «No» в противном случае.

После того, как положение тигра локализовано, программа-решение должна вывести строку, начинающуюся с символа «!», за которым следует целое число m — количество выбранных приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n). Эта строка означает, что внутри выпуклого многоугольника, образованного приёмниками с номерами p1, ..., pm, находится тигр и нет других приёмников.

Ответное сообщение от программы жюри отсутствует, и программа-решение должна немедленно приступать к поиску следующего тигра. Локализовав положение тигра с номером q, программа-решение должна завершить работу.

Тигры не перемещаются во время работы системы обнаружения. Координаты тигров в каждом тесте фиксированы и не меняются в процессе тестирования.

Если существует несколько правильных многоугольников, локализующих положение тигра, можно вывести любой из них.

На рисунке продемонстрирована процедура локализации положения каждого из тигров из приведенного ниже примера.

Примечание

Приведённые примеры иллюстрируют взаимодействие программы-решения с программой жюри «по шагам», для чего в них добавлены дополнительные пустые строки. При реальном тестировании лишние пустые строки вводиться не будут, выводить пустые строки также не требуется.

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.

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

В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.

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

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 5000 ) - количество палочек на столе. Каждая из следующих N строк содержит 4 целых числа x 1 , y 1 , x 2 , y 2 ( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ), обозначающих крайние точки палочек.

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

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

Примеры
Входные данные
4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3
Выходные данные
2 4 1 3 
Входные данные
4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1
Выходные данные
4 3 1 2 
Входные данные
3
4 6 5 5
2 1 15 1
3 2 8 7
Выходные данные
2 3 1 

Страница: << 5 6 7 8 9 10 11 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест