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

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

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

В первой строке вводится N (3≤N≤1000) – число вершин многоугольника. В последующих N строках идут координаты (Xi, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi – целые числа, по модулю не превосходящие 106.

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

Вывести одно число – искомое количество точек.

#397
Цена и длина
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В саду растут деревья. У каждого есть цена и длина. Чтобы построить забор какой-то длины L, нужно срубить деревьев с суммарной длиной L или больше. Нужно, срубив некоторые деревья, построить забор вокруг оставшихся. При этом нужно потратить как можно меньше денег. Если таких способов несколько, нужно выбрать тот, в котором деревьев рубится меньше. Если и таких несколько, выведите любой. Деревья считаются имеющими нулевой радиус.

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

Во входном файле записано число деревьев N (2 <= N <= 14), а затем каждое дерево описано четырьмя числами xi, yi, vi, li - координаты (целые от -10000 до 10000), цена и длина (от 0 до 10000).

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

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

Примеры
Входные данные
5
0 0 1000 11
0 3 1000 11
3 0 1000 11
3 3 1000 11
1 1 100  12
Выходные данные
Cut these trees: 5
Extra wood: 0.00
Входные данные
2
100 100 100 100
0   1   100 100
Выходные данные
Cut these trees: 1
Extra wood: 100.00
#445
Площадь треугольника
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные

Шесть чисел - координаты трёх вершин треугольника. Все числа целые, не превышающие по модулю 1000.

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

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

Примеры
Входные данные
1 1 2 4 3 2
Выходные данные
2.50000
#446
Площадь многоугольника
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Сначала вводится число N - количество вершин многоугольника (3<=N<=100), затем N пар целых чисел, задающих координаты его вершин.

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

Выведите площадь многоугольника не меньше, чем с 3 знаками после десятичной точки.

Примеры
Входные данные
3
1 1
1 4
7 4
Выходные данные
 9.00000000000000E+0000
#451
Принадлежность точки выпуклому многоугольнику
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Задан многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника. В этой задаче многоугольник выпуклый.

Решите задачу быстрым методом

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

Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.

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

Выведите сообщение YES, если точка лежит внутри многоугольника, или NO в противном случае. Гарантируется, что точка не лежит на границе многоугольника.

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