Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Элементарная геометрия
---> 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 >> Отображать по:
#1398
Окружности
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Напишите программу, которая по координатам центров окружностей и их радиусам найдет пару пересекающихся окружностей.

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

В первой строке входного файла содержится целое числоN (1≤N≤10 000) . В каждой из последующих N строк содержатся три натуральных числа X, Y, R меньших 10 000, которые задают координаты центра окружности (X, Y) и его радиус R.

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

Единственная строка выходного файла должна содержать пару номеров пересекающихся окружностей, либо единственное число 0, если никакие две окружности не пересекаются. Окружности нумеруются соответственно порядку во входном файле, начиная с 1 до N. Если существует несколько пар пересекающиеся окружностей, выведите любую из них. Элементы пары могут быть выведены в произвольном порядке.

Примеры
Входные данные
5
5 10 4
6 20 3
10 15 3
12 8 2
13 13 1
Выходные данные
5 3
#1666
Супермногоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

  3. Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).

Формат входных данных

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

Формат выходных данных

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

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

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

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000
#3294
Параллелограмм (6-9)
  

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

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

Напомним, что параллелограммом называется четырехугольник, противоположные стороны которого равны и параллельны.

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

В первой строке входного файла записано целое число \(N\) (\(1 \leq N \leq 10\)) - количество заданных Петей вопросов. Каждая из \(N\) последующих строк содержит описание четырех точек - четыре пары целых чисел \(X\) и \(Y\) (\(-100 \leq X\leq 100\), \(-100\leq Y \leq 100\)), обозначающих координаты точки. Гарантируется, что четыре точки, о которых идет речь в одном вопросе, не лежат на одной прямой.

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

Для каждого из вопросов выведите "YES", если четыре заданные точки могут образовать параллелограмм, и "NO" в противном случае. Ответ на каждый из запросов должен быть в отдельной строке без кавычек.

Примеры
Входные данные
3
1 1 4 2 3 0 2 3
1 1 5 2 2 3 3 0
0 0 5 1 6 3 1 2
Выходные данные
YES
NO
YES
#3870
Космический кегельбан
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках (–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i –  1), (–( i – 3), i – 1), …, (i – 1, i – 1).

Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (xc,  yc) и вектор направления движения шара (vx, vy). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (vx, vy). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, xc = –2, yc = –2, vx = 1, vy = 1.

Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению ( xc, yc) и вектору направления движения (vx,  vy) определяет количество кеглей, сбитых шаром.

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

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 ≤ r ≤ 700, 1  ≤ n ≤ 200 000).

Вторая строка входного файла содержит целое число q (1  ≤ q ≤ 109).

Третья строка входного файла содержит два целых числа xc и yc, разделенных ровно одним пробелом (–106≤ xc ≤ 106, –10 6≤ yc, 1000 ×yc < –(r + q) ).

Четвертая строка входного файла содержит два целых числа vx и vy, разделенных ровно одним пробелом (–106≤ vx ≤ 106, 0  < vy ≤ 106).

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

Выходной файл должен содержать одно целое число — количество сбитых кеглей.

Примечание

Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).

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

Потестовая.

Примеры
Входные данные
500 4
1000
-2 -2
1 1
Выходные данные
7
#3881
Пересечение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

На первой строке входного файла находится число \(K\) — количество тестов во входном файле. Далее идёт описание \(K\) тестов. Каждый тест задаётся описанием двух многоугольников, которые надо проверить на пересечение. Каждый многоугольник задаётся в следующем формате: сначала указывается одно число \(N_i\) — число вершин этого многоугольника, после чего идут \(N_i\) строк, каждая из которых содержит два разделённых пробелом числа \(x_{ij}\) и \(y_{ij}\) — координаты \(j\)-й вершины этого многоугольника. Вершины перечислены в порядке обхода многоугольника.

Число пар многоугольников в одном тесте \(1 \leq K \leq 10\), число вершин каждого многоугольника \(3 \leq N_i \leq 100\), координаты вершин — целые числа, \(|x_{ij}|, |y_{ij}| \leq 10\,000\).

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

Для каждой пары многоугольников выведите в выходной файл на отдельной строке одно слово: “YES”, если многоугольники пересекаются, и “NO”, если нет.

Примеры
Входные данные
2
3
0 0
-1 0
0 -1
3
1 1
2 1
1 2
4
0 0
2 0
2 2
0 2
4
1 1
3 1
3 3
1 3
Выходные данные
NO
YES
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест