--->
144 задач
<---
Источники
#111271
Темы:
[Элементарная геометрия]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2012,
Лига А,
Задача F
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
6 megabytes
На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он находится на круглой обзорной площадке и желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок внутри этой площадки так, чтобы суммарная площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой на обзорной площадке была как можно больше.
Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Если объекты загораживают друг друга, то этим также нужно пренебречь и считать площади независимо.
Входные данные
В первой строке входного файла находятся число T — количество тестов (1 ≤ T ≤ 105). Далее следуют описания тестов. В первой строке каждого описания содержится 4 числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. В третьей строке записаны три числа x0, y0, R — координаты центра круговой площадки и её радиус. Все числа целые, по модулю не превосходящие 1 000. Радиус положителен.
Гарантируется, что отрезки невырождены и не пересекаются с круговой площадкой. Также гарантируется, что они не имеют общих внутренних точек.
Выходные данные
Для каждого теста выведите координаты точки внутри круга, удовлетворяющей условию задачи. Если таких точек несколько, то выведите любую из них. Координаты следует выводить с как можно бóльшим числом знаков после десятичной точки. Соответствующая сумма площадей должна отличаться от правильного ответа по абсолютной или относительной величине не больше чем на 10 - 6.
Примеры тестов
Входные данные
1
0 0 1 0
0 0 -1 0
0 2 1
Выходные данные
0.0000000000 3.0000000000
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
После постройки станции метро Адмиралтейская, правительство Санкт-Петербурга решило построить по-настоящему глубокую станцию, которая будет самой глубокой в мире. Она будет расположена на глубине d метров под землей! Станция будет построена прямо под Смольным собором и будет предназначена для использования только должностными лицами. Департамент городского развития использует свою систему координат для этого проекта. Центром этой системы координат является Смольный собор и третья координата обозначает глубину. Соответственно, новая станция будет иметь координаты (0, 0, d).
Из-за соображений безопасности вестибюль станции должен быть расположен снаружи Смольного монастыря, в точке (x, y). Ваша задача — помочь правительству с постройкой эскалаторов. Станция будет использовать инновационные эскалаторы, которые идут вниз под углом 
. Возможна постройка промежуточного подземного вестибюля и двух эскалаторов. Вам даны x, y и d, найдите координаты промежуточного вестибюля. Заметьте, что вы не можете ничего строить на глубине, большей чем d, так что промежуточный вестибюль должен быть не глубже, чем основная станция.
Входные данные
Единственная строка входного файла содержит три целых числа: x, y и d — координаты вестибюля станции в системе Департамента городского развития и глубина станции ( - 10 000 ≤ x, y ≤ 10 000; (x, y) ≠ (0, 0); 106 ≤ d ≤ 10 000).
Выходные данные
Выведите три числа с точностью не менее, чем 10 знаков после десятичной точки: координаты промежуточного вестибюля в системе координат Департамента городского развития.
Если невозможно построить эскалаторы, выведите "Impossible". Если промежуточный вестибюль не требуется, выведите "Single staircase".
Примеры тестов
Входные данные
0 100 300
Выходные данные
0.0 200.0 100.0
Входные данные
300 400 500
Выходные данные
Single staircase
Входные данные
400 400 500
Выходные данные
Impossible
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Геральд потратил несколько часов, рисуя прямоугольную сетку на листе бумаги. Сначала он нарисовал несколько вертикальных линий на одинаковом расстоянии dx между ними. После этого он нарисовал несколько горизонтальных линий. Они также находились на одинаковом расстоянии dy друг от друга.
Пока Геральд отдыхал от трудов, его брат Майк пришел и нарисовал прямую линию на листе бумаги. Геральд разозлился и приказал Майку стереть все лишнее с бумаги.
Но Майк не воспринял всерьез слова брата и стер все. Но он заметил, что точки пересечения его линии с сеткой были достаточно жирными для того, чтобы быть заметными даже после стирания.
Помогите Геральду восстановить параметры исходной сетки.
Входные данные
Первая строка входного файла содержит одно целое число n — количество точек пересечения (3 ≤ n ≤ 100 000).
Каждая из следующих n строк содержит два целых числа xi, yi — координаты одной из точек пересечения. Координаты не превосходят 109 по абсолютной величине.
Все точки пересечения различны. Других общих точек, кроме описанных выше, у сетки и прямой Майка нет.
Выходные данные
Выведите шесть целых чисел x1, x2, dx, y1, y2 и dy. Первые три числа описывают набор вертикальных прямых: минимальная x-координата вертикальной прямой, максимальная x-координата вертикальной прямой и расстояние между соседними вертикальными линиями ( - 109 ≤ x1 ≤ x2 ≤ 109; 0 < dx ≤ 2·109). Следующие три числа аналогично описывают набор горизонтальных линий ( - 109 ≤ y1 ≤ y2 ≤ 109; 0 < dy ≤ 2·109).
Гарантируется, что хотя бы одно решение существует.
Примеры тестов
Входные данные
4
1 1
5 3
3 2
9 5
Выходные данные
1 9 4 2 5 3
#111494
Темы:
[Элементарная геометрия]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2013,
2 день,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Юный футболист Митя обнаружил на школьном футбольном поле две различные окружности, нарисованные едва заметной белой краской. Вспомнив истории о загадочных кругах на полях, он отметил эти окружности с помощью небольших камушков. Митя разложил на поле n камушков так, чтобы каждый из них находился на одной из окружностей или даже на их пересечении, если эти окружности пересекаются. Получилось так, что на каждой окружности размещался хотя бы один камушек. Обладая великолепным глазомером, Митя расположил камушки на окружностях абсолютно точно, без какой-либо погрешности.
На следующий день пошел дождь, краска стерлась, и нарисованные окружности исчезли, но все камушки остались на своих местах. Теперь Мите очень нужно найти доказательство необычного явления, свидетелем которого он был, то есть, восстановить окружности.
Требуется написать программу, которая по координатам камушков на поле находит вариант размещения их на двух несовпадающих окружностях.
Входные данные
Первая строка входного файла содержит целое число n — количество размещенных Митей камушков на поле (\(2 \leq n \leq 2000\)). Последующие n строк содержат целочисленные координаты (\(x_i\), \(y_i\)) камушков — по одной паре координат, разделенных пробелом, в каждой строке (\(−10^6 \leq x_i, y_i \leq 10^6\)). Никакие два камушка не размещаются в одной точке.
Гарантируется, что ответ для заданного набора камушков существует.
Выходные данные
Выходной файл должен содержать две строки. Первая строка должна содержать последовательность номеров всех камушков, которые принадлежат первой окружности, вторая строка — последовательность номеров всех камушков, которые принадлежат второй окружности.
Каждый камушек должен встречаться хотя бы в одной из двух последовательностей. Если камушек встречается в обеих последовательностях, то это обозначает, что он находится на пересечении окружностей. Считается, что камушки пронумерованы от 1 до n в порядке их следования во входных данных.
Нумерация окружностей не имеет значения, то есть выводить две последовательности можно в любом порядке. Числа в последовательностях можно также выводить в произвольном порядке. Каждая из последовательностей должна содержать не менее одного числа. Все числа в строках должны быть разделены пробелами.
Если вариантов расположения окружностей несколько, можно выбрать любой из них.
Система оценивания
Правильные решения для тестов, в которых 2 ≤ n ≤ 50, будут оцениваться из 50 баллов.
Примеры
Входные данные
7 1 -1 0 0 1 1 3 1 3 -1 2 0 4 0
Выходные данные
1 2 3 6 4 5 6 7
Входные данные
5 -1000000 0 0 1000000 1000000 0 0 -1000000 0 0
Выходные данные
1 2 3 4 5
#111500
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
На плоскости заданы дуга окружности, отрезок и точка. Как отрезок, так и дуга окружности непрозрачны. Определите, какая часть дуги видна из этой точки.
Входные данные
Входной файл состоит из трёх строк, описывающих данные объекты. Первая строка описывает дугу и содержит пять чисел — координаты центра дуги, радиус дуги, полярный угол точки начала дуги и полярный угол точки конца дуги. Полярные углы заданы в градусах
и отсчитываются относительно центра дуги против часовой стрелки от положительного направления оси \(x\). Вторая строка описывает точку и содержит два числа — её координаты. Третья строка описывает отрезок и содержит четыре числа — координаты
начала и конца отрезка. Все числа во входном файле вещественны и не превосходят \(10^6\) по модулю. Гарантируется, что как радиус окружности, так и длина отрезка больше нуля, что полярный угол конца дуги больше, чем полярный угол начала, и
что разность этих углов не превосходит 360.
Гарантируются, что никакие два из данных трёх объектов не имеют общих точек.
Выходные данные
Выведите в выходной файл одно число на отрезке от 0 до 1 — относительную часть дуги, которая видна из данной точки. Ваш ответ должен отличаться от правильного не более, чем на 10−4.
Примечание
Система оценивания: - Группа тестов 1 (40 баллов). В этой группе во всех тестах дуга либо полностью видна, либо полностью не видна.
- Группа тестов 2 (60 баллов). Нет ограничений. Только при прохождении группы 1.
Примеры
Входные данные
2 1 2 120 420 3 6 2 4 2.5 4
Выходные данные
0.496842552858631315
Выбрано
:
|