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

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

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

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

Cначала вводится целое число N - количество деревьев (1≤N≤50000). Затем идут два числа, задающих координаты наблюдателя. Затем идет N троек чисел, задающих деревья  (первые два числа тройки задают координаты центра, а третье - радиус). Все координаты задаются точно и выражаются вещественными числами, по модулю не превосходящими 100000 и записанными не более чем с 2 знаками после десятичной точки.

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

В первой строке выведите сообщение YES, если лес является дремучим, и NO  - иначе. Во втором случае во вторую строку необходимо вывести координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель, не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.

Примеры
Входные данные
4
1 1
7 7 6
-4 6 5
6 -4 5
-5 -5 6
Выходные данные
YES
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
На плоскости заданы углы (фигура, образованная лучами, исходящими из одной точки). Требуется найти "выпуклую оболочку", которая также ограничена двумя лучами.

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек $X$, называется выпуклой оболочкой множества $X$.

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

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

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

В первой строке вводится число $n$ - количество углов (1 <= $n$ <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают $10^4$ по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

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

Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить $10^5$ по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа. На первой строке выведите $L$ - количество объектов в ответе. Следующие $L$ строк должны содержать описание объектов. Объекты описываются следующим образом:

*Отрезок: "segment $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - концы отрезка, отрезок считается направленным от ($x_1$, $y_1$) к ($x_2$, $y_2$).
*Луч, направленный от начала: "outray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) - начало луча, а ($x_2$, $y_2$) - произвольная точка на луче, отличная от начала.
*Луч, направленный к началу: "inray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_2$, $y_2$) - начало луча, а ($x_1$, $y_1$) - произвольная точка на луче, отличная от начала.
*Прямая: "line $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - две точки на прямой, причем при движении вдоль прямой в ее направлении точка ($x_1$, $y_1$) следует ранее точки ($x_2$, $y_2$).
*Если выпуклой оболочкой является вся плоскость, то выведите $L$ = 0.

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

Многоугольник на плоскости задан целочисленными координатами своих $N$ вершин в декартовой системе координат. Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

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

В первой строке находится число $N$. В следующих $N$ строках находятся пары чисел - координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник. 3 <= $N$ <= 50 000, координаты вершин целые и по модулю не превосходят 20 000.

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

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

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

На плоскости заданы $N$ точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.

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

В первой строке находится число $N$, далее - $N$ строк с парами координат. 3 <= $N$ <= 1000, -10 000 <= $x_i$, $y_i$ <= 10 000, все числа целые, все точки различны.

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

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

Примеры
Входные данные
9
20 40
30 40
30 30
40 30
40 40
50 40
50 20
35 20
20 20
Выходные данные
100.0

Есть замок — точка $(0, 0)$. Замок окружен несколькими непересекающимися заборами, каждый представляет из себя выпуклый многоугольник.

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

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

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

8 первой строке задано число $N$ ($1 \leq N \leq 100\,000$). Далее следуют описания $N$ заборов. Каждое описание начинается с числа $K$, далее следуют $К$ строк, содержащих по два числа $X$ и $Y$ — координаты вершин ($0 \leq X,Y \leq 2\cdot10^6$). Вершины каждого многоугольника перечисляются в порядке обхода против часовой стрелки. Гарантируется, что точка $(0, 0)$ лежит внутри каждого забора.

Далее следует число $M$ ($0 \leq M \leq 100\,000$) — количество захватчиков. В следующих $М$ строках заданы координаты захватчиков.

Суммарное число вершин во всех многоугольниках не превосходит $100\,000$.

Все вводимые числа являются целыми.

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

Выведите единственное число — общую захваченную площадь с шестью знаками после десятичной точки.

Примеры
Входные данные
3
4
-10 -10
10 -10
10 10
-10 10
4
20 20
-20 20
-20 -20
20 -20
4
30 -30
30 30
-30 30
-30 -30
3
1 1
22 23
111 123
Выходные данные
2400.0

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