--->
144 задач
<---
Источники
#419
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Одной из первоочередных задач, стоящих перед министерством обороны Флатландии, является модернизация вооружения. В связи с этим было решено построить новый испытательный полигон.
По форме полигон представляет собой выпуклый многоугольник. Для демонстрации военных испытаний на полигоне различным чиновникам, неподалеку от него решено было построить наблюдательный центр. В результате длительных исследований было установлено, что основной характеристикой местоположения наблюдательного центра является степень этого центра относительно полигона.
Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: dmin и dmax. Степенью точки относительно данного многоугольника назовем минимум величины dmin×dmax по всем таким лучам.
Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!
Входные данные
Будем считать, что наблюдательный центр находится в точке (0, 0). На вход программы поступает описание полигона.
В первой строке вводится число n – количество вершин полигона ( 3
n100). Следующие n строк содержат по два вещественных числа – координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают 1000 по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.
Выходные данные
Выведите одно число – степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на 10-4.
Примеры
Входные данные
3 1.0 2.0 3.0 2.0 0.5 3.25
Выходные данные
7.0000000000
#423
Темы:
[Алгоритм Дейкстры]
[Элементарная геометрия]
Даны две пересекающихся окружности. Необходимо найти кратчайший путь от точки до точки по окружностям.
Петя любит ездить в школу на велосипеде. Но ездить на велосипеде по тротуарам запрещено, а ездить по дороге опасно. Поэтому Петя ездит только по специальным велосипедным дорожкам. К счастью, и Петин дом, и Петина школа находятся в непосредственной близости от таких дорожек.
В городе, где живет Петя, есть ровно две велосипедных дорожки. Каждая дорожка имеет форму окружности. В точках их пересечения можно переехать с одной дорожки на другую.
Петя знает точку, в которой он заезжает на дорожку, и точку, в которой следует съехать, чтобы попасть в школу. Петю заинтересовал вопрос: какое минимальное расстояние ему следует проехать по дорожкам, чтобы попасть из дома в школу.
Входные данные
Будем считать, что в городе введена прямоугольная декартова система координат.
Первые две строки входных данных описывают велосипедные дорожки. Каждая из них содержит по три целых числа – координаты центра окружности, которую представляет собой соответствующая дорожка, и ее радиус. Координаты и радиус не превышают 200 по абсолютной величине, радиус – положительное число. Гарантируется, что дорожки не совпадают.
Следующие две строки содержат по два вещественных числа – координаты точки, где Петя заезжает на дорожку, и точки, в которой Петя съезжает с дорожки. Гарантируется, что каждая из точек с высокой точностью лежит на одной из дорожек (расстояние от точки до центра одной из окружностей отличается от ее радиуса не более, чем на 10-8). Точки могут лежать как на одной дорожке, так и на разных.
Выходные данные
Выведите минимальное расстояние, которое следует проехать Пете по велосипедным дорожкам, чтобы попасть из дома в школу. Ответ должен отличаться от правильного не более, чем на 10-4.
Если доехать из дома до школы по велосипедным дорожкам невозможно, выведите число -1.
Примеры
Входные данные
0 0 5 4 0 3 3.0 4.0 1.878679656440357 -2.121320343559643
Выходные данные
8.4875540166
Входные данные
0 0 5 4 0 3 4.0 3.0 4.0 -3.0
Выходные данные
6.4350110879
Входные данные
0 0 4 10 0 4 4.0 0.0 6.0 0.0
Выходные данные
-1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На плоскости даны две прямые. Каждая прямая задается парой точек, через которые она проходит. Требуется установить, пересекаются ли эти прямые, и найти координаты точки пересечения.
Входные данные
Вводятся сначала координаты двух различных точек, через которые проходит первая прямая, а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек, через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.
Выходные данные
Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2. Если прямые пересекаются ровно в одной точке, то выведите сначала число 1, а затем два вещественных числа - координаты точки пересечения.
Примеры
Входные данные
0 0 1 1 1 0 -1 2
Выходные данные
1 5.0000000E-0001 5.000000E-0001
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные
Семь чисел - координаты двух точек вне прямой и коэффициенты A, B и C её уравнения.
Выходные данные
Выведите одну строку: "YES", если точки лежат по одну сторону прямой, и "NO" в противном случае.
Примеры
Входные данные
0 1 1 0 0 -4 8
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные
Пять чисел - коэффициенты A, B и C уравнения прямой и координаты некоторой точки X, Y (точка может быть как на прямой, так и вне ее). Все числа целые, по модулю не превосходят 1000.
Выходные данные
Выведите три числа - коэффициенты A, B и C уравнения прямой, перпендикулярной заданной и проходящей через заданную точку. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.
Примеры
Входные данные
0 -4 8 5 0
Выходные данные
-4.00000 0.00000 20.00000
Выбрано
:
|