--->
144 задач
<---
Источники
#488
Темы:
[Элементарная геометрия]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2006,
2 день,
Задача C
]
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
На плоскости дано множество отрезков. Требуется найти прямую, которая пересекла бы наибольшее возможное количество из данных отрезков и при этом проходила бы как минимум через две точки с целочисленными координатами.
Считается, что прямая пересекает отрезок, если она имеет с ним хотя бы одну общую точку (т.е. она может проходить через конец отрезка, внутреннюю точку отрезка, либо содержать весь отрезок).
Формат входных данных
Сначала вводится число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел Xi1, Yi1, Xi2, Yi2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.
Заданные отрезки могут пересекаться, иметь общие части, один из них может полностью содержаться внутри другого. Отрезки имеют ненулевую длину.
Формат выходных данных
Выведите координаты каких-нибудь двух точек, через которые проходит прямая, пересекающая наибольшее количество отрезков. Координаты точек должны быть целыми и не должны по модулю превышать 107.
Примеры
|
Входные данные |
Выходные данные |
Пояснение (кол-во отрезков, пересекаемых прямой) |
|
3 |
0 -1 1 4 |
3 |
|
2 |
0 0 1 0 |
2 |
|
2 |
1 0 1 1 |
2 |
|
5 |
10 3 1 4 |
4 |
#493
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2007,
1 день,
Задача D
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.
Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.
Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).
Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).
Главный Судья гонок хочет определить порядок, в котором должны стартовать скутеры, чтобы аварии не произошло. Например, в ситуации, приведенной на рисунке, сначала должен стартовать скутер номер 2 (если попытается стартовать скутер номер 1 или 3, то он столкнется со скутером номер 2). После этого скутеры 1 и 3 могут стартовать в любом порядке (они друг другу не мешают).
Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.
Входные данные
В первой строке вводится натуральное число
В каждой из следующих N строк содержится по 6 чисел: x1, y1, x2, y2, x3, y3 – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 106. В начальный момент скутеры не задевают друг друга.
Выходные данные
Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.
Примечание: первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным
Примеры
Входные данные
3 1 19 3 9 6 15 5 6 10 2 10 12 1 1 6 1 3 7
Выходные данные
Входные данные
3 0 1 -2 1 -1 -1 5 6 10 2 10 12 1 1 6 1 3 7
Выходные данные
#496
Темы:
[Элементарная геометрия]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2007,
2 день,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.
Входные данные
В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).
В каждой из следующих N строк записаны по два числа xi, yi – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 106. Некоторые точки могут совпадать.
Выходные данные
Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.
Примеры
Входные данные
1 0 0
Выходные данные
5.6568542495
Входные данные
2 1 1 1 2
Выходные данные
7.6568542495
#519
Темы:
[Алгоритм Дейкстры]
[Элементарная геометрия]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с \(N\) вершинами. Сам Петя находится в точке с координатами (\(x\), \(y\)).
Петя хочет увидеть свет. Для этого ему необходимо оказаться в такое точке, что отрезок, соединяющей ее с началом координат, не пересекается с домом Пети (но может его касаться, в частности, проходить вдоль стороны многоугольника дома).
Петя может перемещаться по плоскости со скоростью \(v\). Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).
Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.
Входные данные
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10-2\( \le\) v\( \le\) \(10^4\).
Вторая строка содержит \(N\) – число вершин в многоугольнике, задающем Петин дом ( 3\( \le\)N\( \le\)100). Далее в \(N\) строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.
Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10-2, расстояние от Пети до начала координат не меньше 10-2.
Выходные данные
Выведите минимальное время, за которое Петя сможет попасть в освещенную точку. Ваш ответ должен отличаться от правильного не более чем на 10-4.
Примеры
Входные данные
3.5 3.5 1.0 4 2.0 0.0 4.0 2.0 2.0 4.0 0.0 2.0
Выходные данные
3.58113883008418967000
#549
Темы:
[Элементарная геометрия]
ограничение по времени на тест
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
Выбрано
:
|