Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Fencing the Herd#90407

Фермер Джон нуждается в Вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с Вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать Вам вопросы про варианты изгороди, на которые Вы должны отвечать YES, если изгородь подходит и NO, в противном случае.

Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.

Формат входных данных

Первая строка ввода содержит N (1 <= N <= 100,000) and Q (1 <= Q <= 100,000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.

Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и y (разделённые пробелом), представляющие позицию очередной коровы.

Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C

Все позиции коров уникальны и (-10^9 <= x, y <= 10^9). Кроме того, -10^9 <= A, B <= 10^9 and -10^18 <= C <= 10^18. Никогда не будет изгороди с A = B = 0.

Формат выходных данных

Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.

геометрия

—Войти и решать

Lights Out#90385

Фермер Джон установил новую доильную машину. Она берёт так много энергии, что в амбаре часто выключается свет. Это случается так часто, что Беси запомнила карту амбара. Это позволяет ей быстрее находить путь к выходу в темноте. Теперь ей интересно узнать насколько дольше её путь в темноте.

Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами $(x_1, y_1) \ldots (x_n, y_n)$ перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке $(x_1, y_1)$. Беси начинает в некоторой вершине $(x_i, y_i)$ для $i > 1$. Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.

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

Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.

ФОРМАТ ВВОДА (файл lightsout.in):

Первая строка ввода содержит $N$ ($4 \leq N \leq 200$). Каждая из последующих $N$ строк содержит по два целых числа, описывающих точки $(x_i, y_i)$ в почасовом порядке обхода. Все целые числа $-100,000 \ldots 100,000$.

ФОРМАТ ВЫВОДА (файл lightsout.out):

Минимально возможное для худшего случая увеличение длины оптимального пути при походе в темноте по сравнению с походом при свете.

геометрия Задача на реализацию Разбор случаев

—Войти и решать

Cow Rectangles#90372

Заданы координаты N коров ФД (1 <= N <= 500) на 2D-плоскости.
Коровы принадлежат двум разным породам: Holsteins и Guernseys.
ФД хочет построить прямоугольную изгородь со сторонами,
параллельными осям координат, содержащими только коров
Holsteins, без Guernseys (корова считается находящейся в этой области,
Даже если она находится на её границе). Среди всех таких изгородей
ФД хочет выбрать ту, которая будет содержать максимальное количество
коров породы Holsteins. А среди всех таких изгородей ФД хочет выбрать
изгородь с минимальной площадью. Пожалуйста, определите эту площадь.
Допускается изгородь с нулевой высотой или нулевой шириной.

Формат входных данных

Первая строка ввода содержит целое число N. Каждая из следующих N
строк описывает корову двумя целыми числами и одним символом.
Целый числа указываю координаты коровы (x,y) (0 <= x, y <= 1000),
А символ H или G - определяет породу этой коровы. Никакие две коровы
не могут находится в одной точке. И есть хотя бы одна корова типа Holstein.

Формат выходных данных

Выведите два целых числа. Первая строка должна содержать максимальное
число коров породы Holsteins, которые можно огородить так, чтобы
там не было ни одной коровы типа Guernseys. Вторая строка должна содержать
минимальную площадь, огороженную этой изгородью.

геометрия

—Войти и решать

Table Recovery#90312

Перед Беси находится $N\times N$ ($1\le N\le 1000$) таблица сложения, где целое число в ячейке строки $r$ и столбца $c$ есть $r+c$, для всех $1\le r,c\le N$. Например, для $N=3$, эта таблица выглядит так:

2 3 4
3 4 5
4 5 6

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

Поменять две строки
Поменять два столбца
Выбрать два значения $a$ и $b$ из присутствующих в таблице, а затем одновременно поменять все вхождения $a$ на $b$ и все возможные вхождения $b$ на $a$.

Эльза всегда выполняет операции в порядке возрастания типа: сначала все операции (возможно ни одной) типа $1$, затем типа $2$, затем типа $3$.

Помогите Беси восстановить возможное состояние таблицы после того как Эльза выполнит все операции типов $1$ и $2$, но прежде чем она выполнит первую операцию типа $3$. Если возможно много вариантов ответов выберите лексикографически минимальный.

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

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит $N$.

Каждая из следующих $N$ строк содержит $N$ целых чисел, представляющих таблицу сложения Беси после того, как Эльза перепутала её.

ФОРМАТ ВЫВОДА (на экран / stdout):

Лексикографически минимальное состояние таблицы после всех операций типа $1$ и $2$, но перед выполнением первой операции типа $3$. Гарантируется, что ответ существует.

геометрия

—Войти и решать

Photo Op#90304

Ферма Фермера Джона полна пышной растительности и каждая корова хочет получить фото этой естественной красоты. К сожалению, Беси еще есть куда пойти, но она не хочет мешать фотосессиям.

Беси расположена в точке $(X,0)$ на координатной XY-плоскости и хочет попасть в точку $(0,Y)$ ($1\le X,Y\le 10^6$). К несчастью, $N$ ($1 \leq N \leq 3 \cdot 10^5$) других коров решили позировать на оси $X$. Точнее, корова $i$ находится в точке $(x_i,0)$ а фотограф находится в точке $(0,y_i)$ где $(1 \leq x_i,y_i \leq 10^6)$ и он приготовился делать снимок. Они начинают съёмки перед моментом времени $s_i$ ($1 \leq s_i < T$) и фоткаются очень долго, $1\le T\le N+1$.

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

Если Беси выходит в момент времени $t$, она избежит линии обзора для всех пар корова/фотограф, которые начинают позировать в момент времени $s_i \le t$, и пусть расстояние к её конечной точке равно $d_t$. Определите величины $\lfloor d_t\rfloor$ для каждого целого $t$ от $0$ до $T-1$ включительно.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка ввода содержит $N$ и $T$, представляющие количество коров на оси $x$ и временной интервал в течение которого Беси может начать свой поход.

Вторая строка содержит $X$ и $Y$, представляющих стартовую $X$-позицию Беси и финишную $Y$-позицию, соответственно.

Последующие $N$ строк содержат $s_i$ $x_i$ $y_i$. Гарантируется, что все $x_i$ различны и все $y_i$ различны. Все $s_i$ будут заданы в порядке возрастания, где $s_i \leq s_{i+1}$.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите $T$ строк, где $t$-ая строка (0-индексированная) содержит $\lfloor d_t\rfloor$.

геометрия

—Войти и решать

Target Practice II#90258

Замечание: время на тест 2.5 сек, по умолчанию 1.25.

Замечание: необходимо использовать 64-битные типы данных (например "long long" в C/C++).

Фермер Джон тренирует своих коров стрельбе из лука следующим упражнением на координатной плоскости.

Всего имеется $N (1 \leq N \leq 4 \cdot 10^4)$ прямоугольных мишеней со сторонами параллельными осям координат и $4N$ коров. Каждая корова должна быть назначена различной вершине прямоугольника. В момент $i$, для $1 \leq i \leq N$:

Цель $i$ появляется.
$4$ коров, назначенные своим вершинам, стреляют по ним.
Если выстрел коровы попадает во внутренность мишени, прежде чем он попадёт в назначенную вершину или пройдёт мимо, корова не выполнила упражнение.
Мишень исчезает, чтобы освободить место для следующей мишени.

Каждая корова расположена на $y$-оси $(x = 0)$, и каждая мишень - это прямоугольник, где мишень $i$ имеет нижний левый угол в точке $(X_1, y_1^{(i)})$ и правый верхний угол в точке $(x_2^{(i)}, y_2^{(i)})$. Эти координаты также удовлетворяют условиям $1 \leq X_1 < x_2^{(i)}\leq 10^9$ и $1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9$ (Замечание: $X_1$ одно и то же для каждой мишени).

В дополнение, каждая корова имеет свой "фокусный угол", где она может работать. Поэтому корова поворачивается на этот специфический угол, когда стреляет. Полагая, что их стрела летит по прямой от их позиции к назначенной вершине траектория стрелы $i$'-ой коровы может быть описана $s_i$ $(0 < |s_i| < 10^9)$, наклоном траектории.

ФД хочет минимизировать расстояние между самыми дальними коровами. Если ФД оптимально назначит каждой корове её целевую вершину и оптимально разместит их на оси $y$, вычислите минимальное расстояние между самыми дальними коровами или коровы всегда не выполнят упражнение.

Каждый тест содержит $T$ ($1 \leq T \leq 10$) независимых подтестов. Гарантируется, что сумма всех $N$ по всем подтестам не превысит $4\cdot 10^4$.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит $T$ ($1 \leq T \leq 10$), количество независимых подтестов. Каждый подтест задаётся следующим образом:

Первая строка подтеста содержит два целых числа $N$ и $X_1$, количество мишеней и самую левую координату мишеней соответственно.

Затем следуют $N$ строк, где $i$-ая строка содержит 3 целых числа $y_1^{(i)}$, $y_2^{(i)}$, $x_2^{(i)}$, - нижняя $y$-координата, верхняя $y$-координата и правая $x$-координата $i$-ой мишени соответственно.

Последняя строка состоит из $4N$ целых чисел $s_1, s_2, \dots, s_{4N}$ где $s_i$ обозначает наклон траектории выстрела $i$-ой коровы.

ФОРМАТ ВЫВОДА (на экран / stdout):

Минимальное возможное расстояние между самыми дальними коровами или $-1$ если коровы всегда не справятся с упражнением.

битмаски геометрия

—Войти и решать

Multiple Choice Test#90170

Коровы проходят тест с множественными правильными ответами. Однако вместо стандартного теста, где сделанные выборы оцениваются для каждого теста Индивидуально, а затем результаты суммируются, в этом тесте Ваши выборы суммируются до оценивания.

А именно, Вам даются $N$ ($2\le N\le 10^5$) групп целых векторов на 2D-плоскости, где каждый вектор обозначается упорядоченной парой $(x,y)$. Выберите один вектор из каждой группы так, чтобы сумма векторов была как можно дальше от начала координат.

Гарантируется, что общее количество векторов не более $2\cdot 10^5$. Каждая группа имеет размер не менее $2$ и внутри группы все векторы различны. Также гарантируется, что каждая из координат $x$ и $y имеет абсолютную величину не более $\frac{10^9}{N}$.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит $N$, количество групп.

Каждая группа начинается с $G$, количества векторов в группе, за которой следуют $G$ строк, содержащих вектора этой группы. Последовательные группы разделены пустой строкой.

ФОРМАТ ВЫВОДА (на экран / stdout):

Квадрат максимально возможного Евклидова расстояния от начала координат.

геометрия

—Войти и решать

Equilateral Triangles#90100

Пастбище Фермера Джона может быть представлено $N\times N$ квадратной решёткой $(1\le N\le 300)$, состоящей из позиций $(i,j)$ для всех $1\le i,j\le N$. Для каждого квадрата решётки, соответствующий символ на вводе равен '*', если в этой позиции находится корова (ровно одна) и '.' если нет коров в этой позиции.

ФД считает, что красота пастбища прямо пропорциональна количеству таких троек коров, что их позиции находятся на равных расстояниях друг от друга, другими словами они образуют равносторонний треугольник. ФД считает расстояния не Евклидовые, а Манхэттенские, т.е. расстояние между двумя позициями $(x_0,y_0)$ и $(x_1,y_1)$ равно $|x_0-x_1|+|y_0-y_1|$.

По заданной решётке, определяющей позиции коров, вычислите количество равносторонних троек.

ОЦЕНИВАНИЕ:

будет 14 тестов с такими значениями $N\in \{50,75,100,125,150,175,200,225,250,275,300,300,300,300\}.$

ФОРМАТ ВВОДА (файл triangles.in):

Первая строка содержит одно целое число $N.$

Для каждой из $1\le i\le N,$ строка $i+1$ ввода содержит строку длины $N$, состоящую только из символов '*' и '.'. $j$-ый символ описывает, существует корова в позиции $(i,j)$ или нет

ФОРМАТ ВЫВОДА (файл triangles.out):

Выведите одно целое число, содержащее ответ. Можно доказать, что оно поместится в 32-битное целое.

геометрия

—Войти и решать

Rectangular Pasture#90094

Самое большое пастбище Фермера Джона может быть рассмотрено как большая 2D-решётка из квадратных ячеек (как большая шахматная доска). В настоящий момент $N$ коров занимают некоторые из этих ячеек ($1 \leq N \leq 2500$).

ФД хочет построить изгородь, которая окружит прямоугольный регион ячеек Стороны этого прямоугольника должны быть параллельны осям координат, и он может быть мал, вплоть до одной ячейки. Помогите ФД посчитать количество различных подмножеств коров, которые он может окружить таким регионом. Заметим, что пустое подмножество должно быть рассмотрено как одно из таких подмножеств.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит одно целое число $N$. Каждая из последующих $N$ строк содержит два разделённых пробелом целых числа - указывающих $(x,y)$-координаты ячейки, в которой находится соответствующая корова. Все $x$ координаты различны. Все $y$ координаты различны. Все $x$ и $y$ лежат в интервале $0 \ldots 10^9$.

ФОРМАТ ВЫВОДА (на экран / stdout):

Количество подмножеств коров, которые ФД может огородить. Можно доказать, что это количество поместиться в 64-битное знаковое (например, long long в С/C++).

геометрия

—Войти и решать

Square Pasture#90089

Самое большое пастбище Фермера Джона может быть представлено как 2D-решётка квадратных ячеек (как большая шахматная доска). В настоящий момент $N$ коров занимают некоторые из этих ячеек ($1 \leq N \leq 200$).

ФД хочет построить забор, который огородит квадратный регион ячеек. Стороны этого квадрата должны быть параллельны осям координат. И он может быть маленьким, вплоть до одной ячейки. Помогите ФД посчитать количество различных подмножеств коров, которые он может огородить таким регионом. Заметим, что пустое подмножество также нужно считать.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит одно целое число $N$. Каждая из последующих $N$ строк содержит два разделённых пробелом целых числа, указывающих $(x,y)$ координаты ячейки соответствующей коровы. Все $x$ координаты различны. Все $y$ координаты различны. Все $x$ и $y$ координаты в интервале $0 \ldots 10^9$.

Заметим, что хотя координаты ячеек неотрицательны, квадратная огороженная область может быть распространена на ячейки с отрицательными координатами.

ФОРМАТ ВЫВОДА (на экран / stdout):

Количество подмножеств коров, которые ФД сможет огородить. Можно доказать, что это количество поместится в 32-битное целое.

геометрия

—Войти и решать

Splitting the Field#89968

$N$ коров ($3 \leq N \leq 50,000$) Фермера Джона расположены в различных позициях его двумерного поля. ФД хочет огородить всех коров забором прямоугольной формы со сторонами параллельными осям координат x и y. Он хочет, чтобы забор огораживал всех коров (допускаются коровы на границе забора), и площадь области, ограниченной забором, была минимальной.

В связи с ограниченностью бюджета первоначальный план быт изменён. Теперь ФД хочет огородить всех коров двумя заборами вместо одного. Помогите ФД вычислить минимальную площадь, которую он может ограничить двумя заборами, которые включат вместе всех коров и стороны которых параллельны осям координат. Заборы не могут перекрываться - даже по границам. Заметим, что возможна площадь 0 - если забор имеет нулевую ширину или высоту.

ФОРМАТ ВВОДА (файл split.in):

Первая строка ввода содержит $N$. Каждая из последующих $N$ строк содержит два целых числа, указывающих координаты коровы - положительные целые числа в интервале $1 \ldots 1,000,000,000$.

ФОРМАТ ВЫВОДА (файл split.out):

Выведите целое число - общую площадь, которую ФД может огородить двумя прямоугольниками.

геометрия

—Войти и решать

Hill Walk#89891

Имется N (1 <= N <= 100,000) холмов. Каждый холм имеет форму отрезка из точки (x1, y1) в точку (x2, y2) где x1 < x2 и y1 < y2. Никакие из этих отрезков не пересекаются и не касаются даже в конечных точках. Кроме того, для первого холма справедливо (x1,y1) = (0,0).
Беси начинает свой путь в точке (0,0) на первом холме. Когда Беси попадает на холм, она карабкается вверх пока не достигнет конца холма. Затем она прыгает вниз. Если она приземлится на другой холм, она продолжит карабкание уже на этом холме, иначе она падает в бездну (где y=-бесконечности). Каждый холм (x1, y1) -> (x2, y2) необходимо рассматривать как содержащий точку (x1, y1), но не содержащий точку (x2, y2), поэтому Бэси приземляется на холм, если она падает на него сверху с позиции x = x1, но не приземлится на него, если она падает сверху с позиции x = x2.
Посчитайте общее количество холмов, которых Беси коснется в некоторой точке во время своего путешествия.
PROBLEM NAME: hillwalk
Формат входных данных
* Строка 1: Количество холмов, N.
* Строки 2..1+N: Строка i+1 содержит четыре целых числа (x1,y1,x2,y2) описывающих холм i. Каждое целое число находится в диапазоне 0..1,000,000,000.
Формат выходных данных
* Строка 1: Количество холмов, которых коснется Беси за время своего путешествия.
Примечание
Беси пройдется по холмам #1, #4, #3.

геометрия графы реализация

—Войти и решать

Symmetry#89820

После лекции о современном искусстве, Фермер Джон начал искать геометрические фигуры во всем на своей ферме. Он выписал координаты всех своих N коров (2 <= N <= 1000), каждая из которых занимает уникальную точку на плоскости, и теперь хочет узнать, сколько имеется осей симметрии у данного множества точек. Под осью симметрии, как обычно, понимается прямая, относительно которой множества множества точек по разные стороны этой прямой являются зеркально симметричными. Помогите ФД ответить на этот вопрос.
PROBLEM NAME: symmetry
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..1+N: Строка i+1 содержи два разделенных пробелом целых числа x и y, представляющие координаты i-ой коровы (-10,000 <= x,y <= 10,000).
Формат выходных данных
* Строка 1: количество осей симметрии данного множества точек.
Примечание
Имеется 4 оси симметрии – одна вертикальная, одна горизонтальная, и две диагональных.

геометрия

✓ 0✗ 1—Войти и решать

Горнолыжные соревнования#56663

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

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

За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.

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

Входные данные
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы S_x, S_y, F_x, F_y - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа a_i, b_i, y_i, c_i - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (a_i < b_i, F_y < y_i < S_y, c_i - целое число, 0 ≤ c_i ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

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

геометрия Динамическое программирование Задача на реализацию

—Войти и решать

Точки в многоугольнике#55152

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

Ограничения: 3 <= N <= 10 000, координаты вершин целые и по модулю не превосходят 1 000 000.

Входные данные
В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные
Вывести одно число - искомое количество точек.

геометрия Элементарная геометрия

✓ 1✗ 0—Войти и решать

Бассейн реки#55135

Дана карта рек некоторого континента. Каждая река показана как ломаная линия, которая начинается у истока реки и заканчивается или в точке, где река впадает в другую, или устьем реки. Вершины ломаной - или точки поворота реки, или точки впадения притоков.

Будем рассматривать бассейн реки как выпуклый многоугольник минимальной площади, который содержит реку и все её притоки.

Примечание. Согласно этому определению бассейна реки, одна и та же территория может принадлежать бассейнам различных рек.

Пример. Показан континент с тремя реками. Координаты рек и площади бассейнов даны в таблице.

Название реки	x	y	Площадь бассейна реки без притоков
река 1	6	9	12,5
	5	11
	3	12
	2	10
	1	7

река 2	7	9	1,5
	5	7
	5	5,5

река 3	3	10	9,5
	5	8
	4	6
	5	5,5
	6	5
	3	5

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

Входные данные
Первая строка содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки.

Каждый блок номер i состоит:

из одной строки с k_i - числом вершин ломаной, представляющей реку;
ki строк, содержащих пары вещественных чисел x_j и y_j (1 <= j <= k_i), разделённых пробелом, - координаты точек, описывающих реку.
Ограничения: 1 <= N <= 10, сумма k_i <= 1000, -1000 <= x_j, y_j <= 1000.

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

геометрия Многоугольники. Выпуклые оболочки

✓ 2✗ 0—Войти и решать

Мехико#54701

Город Мехико расположен в прекрасной долине, известной как Долина Мехико, на месте которой много лет назад было озеро. Около 1300 года ацтекские религиозные лидеры выпустили указ о том, что центр озера должен быть засыпан, чтобы построить столицу их империи. В настоящее время озеро полностью осушено.

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

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

*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.
*Маршрут проходит через каждый город ровно один раз.
*Любые два последовательно посещаемых города маршрута обязаны иметь между собой коммерческое соглашение.
*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.
*Чтобы избежать столкновения лодок, маршрут не должен иметь самопересечений.

На рисунке показано озеро и города вокруг него. Тонкие и жирные линии отрезков обозначают коммерческие соглашения между городами. Жирные линии показывают маршрут грузоперевозок, начинающийся в городе 2 и заканчивающийся в городе 5.

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до c по направлению часовой стрелки.
Задание
Напишите программу, которая по заданному числу городов c и списку коммерческих соглашений между городами, найдет маршрут товароперевозок, удовлетворяющий указанным выше условиям.

Ограничения
3 ≤ c ≤ 1000, c – число городов вокруг озера

Входные данные
На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число c.
СТРОКА 2: Содержит целое число n – количество коммерческих соглашений.
СЛЕДУЮЩИЕ n СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.

Выходные данные
Если возможно построить маршрут товароперевозок, выведите c строк, в каждой из которых записано целое число. Эти числа представляют собой порядок посещения городов по маршруту товароперевозок. Если невозможно построить маршрут товароперевозок, удовлетворяющий всем указанным требованиям, выведите одну строку, содержащую отрицательное целое число -1.

Замечание
Если существует несколько маршрутов товароперевозок, удовлетворяющих всем указанным требованиям, выведите любой из них.

геометрия графы Перебор

✓ 1✗ 0—Войти и решать

Коллайдер 2.0#50958

Коллайдер — это установка для изучения столкновений элементарных частиц. При его работе частицы разгоняются до большой скорости. Специальный детектор позволяет фиксировать траектории частиц в виде прямых на горизонтальной плоскости.

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

Для анализа потенциальных столкновений частиц важно, чтобы на каждом фотоснимке были отображены все точки пересечений их траекторий. Камера использует очень дорогие расходные материалы, поэтому площадь каждого фотоснимка необходимо минимизировать.

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

появление новой траектории частицы,
получение фотоснимка камерой, ориентированной по заданной направляющей прямой,

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

Формат входных данных
В первой строке задано одно целое число $n$ ($1 \leqslant n \leqslant 200\,000$) — общее количество событий. В следующих $n$ строках заданы описания событий.

Описание каждого события состоит из пяти элементов. Первый элемент является символом <<+>>, если это событие является появлением новой траектории, или символом <<?>>, если это событие является получением фотоснимка. Последующие четыре элемента — целые числа $x_1$, $y_1$, $x_2$, $y_2$ ($-10\,000 \leqslant x_1, y_1, x_2, y_2 \leqslant 10\,000$) — координаты двух несовпадающих точек. Для событий первого типа указанные точки лежат на траектории частицы. Все траектории различны. Для событий второго типа указанные точки лежат на направляющей прямой камеры.

Формат выходных данных
Пусть $q$ — количество полученных фотоснимков. Выходной файл должен содержать $q$ вещественных чисел — минимальные возможные площади фотоснимков, перечисленные в порядке их получения камерой. Тест будет успешно пройден, если для каждой из $q$ выведенных площадей выполняется условие $\frac{|a - b|}{\max(1, b)} \leqslant 10^{-4}$, где $a$ — площадь, выведенная участником, $b$ — площадь, полученная решением жюри.

Примеры

№	Входные данные	Выходные данные	Иллюстрация
1	6 + 0 0 0 1 + 0 0 1 0 + 1 0 0 2 ? 0 0 0 1 + 2 4 3 6 ? 0 0 1 1	2.0 3.000
2	7 ? 11 4 -7 8 + -2 -2 1 1 ? 0 0 0 1 + 0 1 1 0 + 0 2 2 0 ? 0 0 0 1 ? 0 0 1 1	0.0 0.0 0.25 0.0000000

геометрия графы

✓ 3✗ 5—Войти и решать