Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Элементарная геометрия
---> 31 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#3894
Освещение двора
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Для того, чтобы освещать площадку ночью, на ней надо установить несколько прожекторов. К счастью, у фирмы как раз в наличие есть три регулируемых прожектора, а на территории площадки обнаружились три высоких столба. Было решено на каждый столб повесить по прожектору и отрегулировать их так, чтобы каждый прожектор освещал ровно одну из трёх сторон забора: один прожектор должен освещать одну сторону забора, другой — другую, третий — третью. Никакой прожектор не должен освещать ни миллиметра “чужой” стены.

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

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

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

Первая строка входного файла содержит одно число \(T\) — количество тестовых примеров, которые идут дальше (\(1\leq T\leq 1000\)).

Далее следуют описания \(T\) примеров. В каждом сначала идут шесть чисел \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\), \(y_3\) — координаты вершин площадки, после чего идут шесть чисел \(X_1\), \(Y_1\), \(X_2\), \(Y_2\), \(X_3\), \(Y_3\) — координаты столбов. Гарантируется, что все столбы находятся строго внутри площадки. Гарантируется, что площадь площадки строго больше нуля. Гарантируется, что никакие два столба не совпадают. Все координаты во входном файле целые и не превосходят по модулю \(800\).

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

Выведите в выходной файл \(T\) строк по три числа в каждой: для каждого примера выведите номер стороны забора, на которую должен светить прожектор, находящийся на первом столбе, потом номер стороны, на которую должен светить прожектор со второго столба, и наконец номер стороны, на которую должен светить прожектор с третьего столба.

Первая сторона — та, которая соединяет вершины \((x_1, y_1)\) и \((x_2, y_2)\), вторая — \((x_2, y_2)\) и \((x_3, y_3)\), третья — \((x_3, y_3)\) и \((x_1, y_1)\).

Если решения не существует, выведите в соответствующую строку выходного файла три минус единицы: “-1 -1 -1”.

Примечание

Первый пример соответствует рисунку.

Среди тестов будут такие, в которых \(T\leq 10\); суммарная стоимость таких тестов будет 70 баллов.

Примеры
Входные данные
2
0 0 6 10 12 4
7 4 6 6 8 5
-10 -10 0 10 10 -10
0 1 0 -1 1 1
Выходные данные
2 3 1
3 2 1
#111494
Две окружности
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка входного файла содержит целое число n — количество размещенных Митей камушков на поле (\(2 \leq n \leq 2000\)). Последующие n строк содержат целочисленные координаты (\(x_i\), \(y_i\)) камушков — по одной паре координат, разделенных пробелом, в каждой строке (\(−10^6 \leq x_i, y_i \leq 10^6\)). Никакие два камушка не размещаются в одной точке.

Гарантируется, что ответ для заданного набора камушков существует.

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

Выходной файл должен содержать две строки. Первая строка должна содержать последовательность номеров всех камушков, которые принадлежат первой окружности, вторая строка — последовательность номеров всех камушков, которые принадлежат второй окружности.

Каждый камушек должен встречаться хотя бы в одной из двух последовательностей. Если камушек встречается в обеих последовательностях, то это обозначает, что он находится на пересечении окружностей. Считается, что камушки пронумерованы от 1 до n в порядке их следования во входных данных.

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

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

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

Правильные решения для тестов, в которых 2 ≤ n ≤ 50, будут оцениваться из 50 баллов.

Примеры
Входные данные
7
1 -1
0 0
1 1
3 1
3 -1
2 0
4 0
Выходные данные
1 2 3 6 
4 5 6 7
Входные данные
5
-1000000 0
0 1000000
1000000 0
0 -1000000
0 0
Выходные данные
1 2 3 4 
5
#111500
Дуга, отрезок и точка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На плоскости заданы дуга окружности, отрезок и точка. Как отрезок, так и дуга окружности непрозрачны. Определите, какая часть дуги видна из этой точки.

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

Входной файл состоит из трёх строк, описывающих данные объекты. Первая строка описывает дугу и содержит пять чисел — координаты центра дуги, радиус дуги, полярный угол точки начала дуги и полярный угол точки конца дуги. Полярные углы заданы в градусах и отсчитываются относительно центра дуги против часовой стрелки от положительного направления оси \(x\). Вторая строка описывает точку и содержит два числа — её координаты. Третья строка описывает отрезок и содержит четыре числа — координаты начала и конца отрезка. Все числа во входном файле вещественны и не превосходят \(10^6\) по модулю. Гарантируется, что как радиус окружности, так и длина отрезка больше нуля, что полярный угол конца дуги больше, чем полярный угол начала, и что разность этих углов не превосходит 360.

Гарантируются, что никакие два из данных трёх объектов не имеют общих точек.

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

Выведите в выходной файл одно число на отрезке от 0 до 1 — относительную часть дуги, которая видна из данной точки. Ваш ответ должен отличаться от правильного не более, чем на 10−4.

Примечание
Система оценивания:
  • Группа тестов 1 (40 баллов). В этой группе во всех тестах дуга либо полностью видна, либо полностью не видна.
  • Группа тестов 2 (60 баллов). Нет ограничений. Только при прохождении группы 1.
Примеры
Входные данные
2 1 2 120 420
3 6
2 4 2.5 4
Выходные данные
0.496842552858631315
#112035
Силовое поле
  
ограничение по времени на тест
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
#112773
Вид из окна
  
ограничение по времени на тест
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
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест