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

Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.

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

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

В первой строке входного файла содержится число $n$ (3 ≤ $n$ ≤ 1000) – количество вершин ломаной и два целых числа $x_c$ и $y_c$ – координаты центра масс дракона (-1000 ≤ $x_c$, $y_c$ ≤ 1000). В следующих $n$ строках содержится по два целых числа $x_i$ и $y_i$ (-1000 ≤ $x_i$, $y_i$ ≤ 1000) – координаты вершин ломаной в порядке обхода против часовой стрелки (ось $O_X$ направлена вправо, а ось $O_Y$ – вверх).

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

В первой строке выходного файла выведите число устойчивых положений дракона.

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

Многоугольник топят в жидкости, опуская его из воздуха с постоянной скоростью v метров в минуту. Жидкость разъедает многоугольник со всех сторон с постоянной скоростью c метров в минуту. Для точки ($x$, $y$) внутри многоугольника, опускающейся вместе с ним, выясните, в какой момент разъедающая жидкость доберётся до этой точки.

Граница между воздухом и жидкостью проходит по прямой $y$=0. Жидкость разъедает многоугольник как двумерную фигуру. Многоугольник не поворачивается при опускании в жидкость, и в момент времени 0 он не касается жидкости.

В отличие от многоугольника, который считается двумерным, жидкость существует в трёх измерениях. Поэтому она проникает внутрь «дыр» в многоугольнике. Например, если многоугольник имеет форму «чашки», жидкость проникает «внутрь», как показано на рисунке.

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

В первой строке входного файла записано через пробел пять целых чисел $n$, $x$, $y$, $v$ и $c$ (3 $\le$ $n$ $\le$ 30, −100 $\le$ $x$ $\le$ 100, 1 $\le$ $y$ $\le$ 100, 1 $\le$ $c$ < $v$ $\le$ 100). Следующие $n$ строк описывают вершины многоугольника; $i$-я из них содержит два целых числа $x$ и $y$ через пробел (−100 $\le$ $x$ $\le$ 100, 1 $\le$ $y$ $\le$ 100). Вершины даны в порядке обхода против часовой стрелки. Многоугольник не имеет самопересечений и самокасаний, а точка ($x$, $y$) лежит строго внутри него.

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

Выведите одно число — время, которое потребуется жидкости, чтобы добраться до точки ($x$, $y$), с точностью не менее четырёх знаков после запятой.

Примеры
Входные данные
4 0 50 2 1
-1 10
1 10
1 90
-1 90
Выходные данные
25.8660
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

На плоскости даны $N$ точек. Вам требуется построить выпуклую оболочку данного множества точек. Если $N$ нечетно, то оболочку нужно выводить в порядке обхода по часовой стрелке, иначе — против часовой стрелки.

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

Первая строка содержит количество точек $N$, $1\le N\le 20\,000$. Каждая из последующих $N$ строк содержит два целых числа — координаты $x_i$ и $y_i$. Все числа по модулю не превосходят $10^4$.

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

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

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

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

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

В первой строке входного файла записано целое число $N$ ($3 \leq N \leq 1000$) – количество мин. Во второй строке записано $2\times N$ целых чисел ($N$ пар $x_i$, $y_i$), описывающих координаты каждой мины ($-32000 \leq x_i, y_i \leq 32000$).

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

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

Примеры
Входные данные
9
0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2 
Выходные данные
1 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин ($x_0, y_0$), ($x_1, y_1$), ..., ($x_N, y_N$) в порядке их следования. Координаты вершин ломанной удовлетворяют следующим условиям:

$x_0 < x_1 < x_2 < \dots < x_N$;

$x_i = 0$ для некоторого $0 < i < N$;

$y_0 = y_N = 0$;

$y_0 = y_N = 0$;

для всех $i$ от 1 до ($N – 1$) выполнено условие $y_i > 0$.

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

основание треугольника лежит на оси абсцисс;

основание симметрично относительно начала координат;

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

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

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

Первая строка входного файла содержит целое число $K$ – количество измеренных сечений.

Далее следуют описания каждого из $K$ сечений. В первой строке описания сечения содержится число $N_K$ – количество звеньев ломаной. За ней следуют ($N_K + 1$) строк, каждая из которых содержит пару целых чисел $x_i$ и $y_i$ – координаты вершин ломаной сечения в порядке их следования.

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

Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более $10^{–6}$, что означает следующее. Пусть выведенное число равно $x$, а в правильном ответе оно равно $y$. Ответ будет считаться правильным, если значение выражения $|x – y| / max(1, |y|)$ не превышает $10^{–6}$.

Подзадачи и система оценки

Данная задача содержит пять подзадач.

Подзадача 1 (20 баллов)

$K = 1$, $N_1 \leq 15$, координаты вершин по модулю не превышают 20.

Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 2 (10 баллов)

$1 \leq K \leq 20$, сумма $N_i \leq 2000$, координаты вершин по модулю не превышают $10^4$. Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 3 (20 баллов)

$1 \leq K \leq 20$, сумма $N_i \leq 2000$, координаты вершин по модулю не превышают $10^4$.

Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 4 (10 баллов)

$1 \leq K \leq 1000$, сумма $N_i \leq 10^5$, координаты вершин по модулю не превышают $10^9$. Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 5 (40 баллов)

$1 \leq K \leq 1000$, сумма $N_i \leq 10^5$, координаты вершин по модулю не превышают $10^9$.

Каждый тест для данной подзадачи оценивается отдельно.

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

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