Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия
    Градиентный спуск(1 задач)
    Элементарная геометрия(144 задач)
    Многоугольники. Выпуклые оболочки(38 задач)
    Клеточная геометрия(8 задач)
    Квадродерево(3 задач)
---> 12 задач <---
Источники --> Командные олимпиады --> ВКОШП
    1999(7 задач)
    2000(8 задач)
    2001(8 задач)
    2002(9 задач)
    2003(9 задач)
    2004(10 задач)
    2005(10 задач)
    2006(10 задач)
    2007(11 задач)
    2008(10 задач)
    2009(11 задач)
    2010(11 задач)
    2011(11 задач)
    2012(11 задач)
    2013(11 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 1 2 3 >> Отображать по:
#549
Триангуляция Делоне
  
Источники: [ Командные олимпиады, ВКОШП, 2001, Задача E ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется разбить данный многоугольник на треугольники с вершинами, совпадающими с вершинами многоугольников или находящимися внутри многоугольника, так, чтобы внутри окружностей, описанных вокруг треугольников не лежала ни одна вершина многоугольника.

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

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

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

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

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

В первой строке вводится число \(N\) - количество точек (3 <= \(N\) <= 30) исходного набора. Следующие \(N\) строк содержат по одной паре вещественных чисел - координаты соответствующей точки. Никакие три точки не лежат на одной прямой.

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

Выведите количество различных триангуляций Делоне указанного набора точек.

Примеры
Входные данные
4
0.0 0.0
1.0 0.0
0.0 1.0
1.0 1.0
Выходные данные
2
#574
Выпуклая оболочка
  
Источники: [ Командные олимпиады, ВКОШП, 2007, Задача C ]
ограничение по времени на тест
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
#585
Фонтан
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача C ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В прямоугольном зале с круглыми колоннами (координаты и радиусы колонн заданы) необходимо разместить круглый фонтан максимального радиуса.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.

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

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

В первой строке входных данных содержатся вещественные числа \(X\) и \(Y\), 1 <= \(X\), \(Y\) <= \(10^4\) . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (\(X\), 0), (\(X\), \(Y\)) и (0, \(Y\)).

Во второй строке задается число \(N\) (0 <= \(N\) <= 10) - количество колонн. Следующие \(N\) строк содержат параметры колонн - \(i\)-я строка содержит три вещественных числа \(X_i\), \(Y_i\) и \(R_i\) - координаты центра и радиус \(i\)-й колонны (\(R_i\) <= \(X_i\) <= \(X\)-\(R_i\), \(R_i\) <= \(Y_i\) <= \(Y\)-\(R_i\), 0.1 <= \(R_i\) <= min(\(X\) / 2, \(Y\) / 2); для любых \(i\) ≠ \(j\) sqrt( (\(X_i\) - \(X_j\))2 + (\(Y_i\) - \(Y_j\))2 )>= \(R_i\) + \(R_j\)). Все вводимые числа разделены пробелами.

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

Выведите три вещественных числа: \(X_F\), \(Y_F\) и \(R_F\) - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.

Примеры
Входные данные
10 10
0
Выходные данные
5.000 5.000 5.000
Входные данные
1 1000
0
Выходные данные
0.500 0.500 0.500
Входные данные
10 10
4
1 1 1
9 9 1
1 9 1
9 1 1
Выходные данные
5.000 5.000 4.657
#1109
Мост
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки (x1,1,y1,1), продолжается отрезками (x1,1,y1,1) − (x1,2,y1,2), (x1,2,y1,2)− (x1,3,y1,3), ..., (x1,m−1,y1,m−1) − (x1,m,y1,m) и заканчивается лучом, направленным на север из точки (x1,m,y,m).

Аналогично, правый берег реки начинается лучом, направленным на юг из точки (x2,1,y2,1), продолжается отрезками (x2,1,y2,1) − (x2,2,y2,2), (x2,2,y2,2) − (x2,3,y2,3), ..., (x2,n−1,y2,n−1) − (x2,n,y2,n) и заканчивается лучом, направленным на север из точки (x2,n,y2).

Помогите руководству Флатландии выяснить, мост какой минимальной длины можно построить.

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

Первая строка входного файла содержит целое число m (2 ≤ m ≤ 100). Следующие m строк содержат по два целых числа координаты вершин ломаной левого берега: x1,1, y1,1, x1,2,y1,2, ...,x1,m, y1,m.

Следующая строка входного файла содержит целое число n (2 ≤ n ≤ 100). Следующие n строк содержат по два целых числа координаты вершин ломаной правого берега: x2,1, y2,1, x2,2, y2,2, ..., x2,n, y2,n.

Известно, что x1,1 < x2,1, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят 104 по абсолютной величине

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

Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью 10−5.

Оптимальное положение моста показано на следующем рисунке:


Примеры
Входные данные
4
6 1
3 1
3 0
0 3
3
9 3
2 3
6 5
Выходные данные
1.4142135623730951
#2514
Адронные коллайдеры
  
Источники: [ Командные олимпиады, ВКОШП, 2009, Задача E ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Две страны Байтландия и Флатландия решили объединить свои усилия в исследованиях в области физики высоких энергий и построили \(n\) адронных коллайдеров. Каждый коллайдер имеет форму кольца и находится под землей. При этом можно считать, что толщина каждого из коллайдеров пренебрежимо мала — их можно считать окружностями.

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

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

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

Первая строка входного файла содержит целое число \(n\) (\(1 \le n \le 3\)). Каждая из последующих \(n\) строк содержит описание одного из коллайдеров. Описание коллайдера состоит из трех целых чисел: \(x\), \(y\), \(r\) — координат центра коллайдера и его радиуса (\(|x|\), \(|y|\) \(\le 1000\), \(1\) \(\le r\) \(\le 1000\)). Коллайдеры не имеют общих точек, не лежат один внутри другого, а их центры (если \(n = 3\)) не находятся на одной прямой.

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

В первой строке выходного файла описание искомой границы: координаты центра окружности и радиус. Выводите как можно больше знаков после десятичной точки. При проверке правильности ответа, погрешности, не превышающие \(10^{-5}\), будут игнорироваться.

Координаты центра и радиус окружности не должны превосходить \(10^7\) по абсолютной величине. Гарантируется, что существует решение, удовлетворяющее указанному ограничению.

Примеры
Входные данные
2
2 0 1
-2 0 1
Выходные данные
0.0 0.0 2.23606797749979
Входные данные
3
0 10 1
0 0 2
10 10 3
Выходные данные
5.4 4.85 7.52877812131557
Страница: << 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест