Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Многоугольники. Выпуклые оболочки
---> 38 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
ограничение по времени на тест
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.0 second;
ограничение по памяти на тест
64 megabytes

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

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

На первой строке входного файла находится число K — количество тестов во входном файле. Далее идёт описание K тестов. Каждый тест задаётся описанием двух многоугольников, которые надо проверить на пересечение. Каждый многоугольник задаётся в следующем формате: сначала указывается одно число Ni — число вершин этого многоугольника, — после чего идут Ni строк, каждая из которых содержит два разделённых пробелом числа xij и yij — координаты j-й вершины этого многоугольника. Вершины перечислены в порядке обхода многоугольника.

Число пар многоугольников в одном тесте 1 ≤ K ≤ 10, число вершин каждого многоугольника 3  ≤  Ni  ≤  100, координаты вершин — целые числа,  - 10 000 ≤ xij, yij ≤ 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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Помогите теперь мэру определить, какие шоссе проходят через город.

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

Первая строка входного файла содержит два целых числа: n и m – количество шоссе и количество станций метро, соответственно (1 ≤ n, m ≤ 100 000).

Следующие n строк описывают шоссе. Каждое шоссе описывается тремя целыми числами a, b и c и представляет собой прямую на плоскости, задаваемую уравнением a×x+b×y+c = 0 (|a|, |b|, |c| ≤ 106). Следующие m строк входного файла описывают станции метро. Каждая станция описывается двумя целыми числами x и y и представляет собой точку на плоскости с координатами (x, y) (|x|, |y| ≤ 106).

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

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

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

Система тестов состоит из двух групп:

В тестах первой группы выполняется ограничение $n \le 10^4$. За прохождение этой группы ставится 50 баллов.

В тестах второй группы дополнительных ограничений нет. За прохождение этой группы ставится также 50 баллов.

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

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




Внезапно Лена задумалась — ведь эта игра может стать прекрасной задачей по информатике, достойной финала международной студенческой олимпиады! Её Вам и предстоит решить.

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

Первая строка входного файла содержит T (Первая группа тестов: 0 < T < 11, вторая группа тестов: T = 1) -- количество тестов во входном файле. Далее следуют T тестов. Первая строка теста содержит число N (Первая группа тестов: 3 <= N <= 100. Вторая группа: 3 <= N <= 2 * 105) — количество вершин многоугольника.

Следующие N строк содержат по два числа — xi и yi (Первая группа тестов: 0 <= xi, yi <= 1000. Вторая группа: -105 <= xi, yi <= 105), задающие координаты многоугольника в порядке обхода. Гарантируется, что он не имеет самокасаний и самопересечений.

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

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

Примеры
Входные данные
2
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
Выходные данные
2.4000
14.1422
ограничение по времени на тест
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 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест