Координатная плоскость
На плоскости задано множество точек с целочисленными координатами. Необходимо найти максимально возможную площадь невырожденного (то есть, имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Пример входных данных:
3
6 0
0 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных:
24
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости задано множество точек с целочисленными координатами.
Необходимо найти минимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при
этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Пример входных данных:
3
6 0
0 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных:
24
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости дан набор точек с целочисленными координатами. Необходимо найти такой треугольник наибольшей площади с вершинами в этих точках, у которого нет общих точек с осью Ох, а одна из сторон лежит на оси Оу.
Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от количества точек.
Перед текстом программы кратко опишите используемый алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных
В первой строке вводится одно целое положительное число — количество точек N.
Каждая из следующих N строк содержит два целых числа — сначала координата х, затем координата у очередной точки. Числа разделены пробелом.
Описание выходных данных
Программа должна вывести одно число - максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.
Пример входных данных
8
0 −10
0 2
4 0
3 3
0 7
0 4
5 5
−9 9
Пример выходных данных для приведённого выше примера входных данных: 22.5
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости дан набор точек с целочисленными координатами. Необходимо найти такой треугольник наибольшей площади с вершинами в этих точках, у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох.
Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от количества точек.
Перед текстом программы кратко опишите используемый алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных
В первой строке вводится одно целое положительное число — количество точек N.
Каждая из следующих N строк содержит два целых числа — сначала координата х, затем координата у очередной точки. Числа разделены пробелом.
Описание выходных данных
Программа должна вывести одно число — максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.
Пример входных данных:
8
-10 0
2 0
0 4
3 3
7 0
5 5
4 0
9 -9
Пример выходных данных для приведённого выше примера входных данных:
22 . 5
Загрузка решений доступна для зарегистрировавшихся пользователей
Дан список точек плоскости с целочисленными координатами. Необходимо определить:
1) номер координатной четверти K, в которой находится больше всего точек;
2) количество точек в этой четверти M;
3) точку A в этой четверти, наименее удалённую от осей координат;
4) расстояние R от этой точки до ближайшей оси.
Если в нескольких четвертях расположено одинаковое количество точек, следует выбрать ту четверть, в которой величина R меньше. При равенстве и количества точек, и величины R необходимо выбрать четверть с меньшим номером K. Если в выбранной четверти несколько точек находятся на одинаковом минимальном расстоянии от осей координат, нужно выбрать первую по списку. Точки, хотя бы одна из координат которых равна нулю, считаются не принадлежащими ни одной четверти и не рассматриваются.
Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных
В первой строке вводится одно целое положительное число - количество точек N.
Каждая из следующих N строк содержит координаты очередной точки - два целых числа (первое — координата x, второе — координата у).
Описание выходных данных
Программа должна вывести номер выбранной четверти K, количество точек в ней M, координаты выбранной точки A и минимальное расстояние R по образцу, приведённому ниже в примере.
Пример входных данных:
7
−3 4
1 2
1 1
0 4
−2 −3
−6 8
−12 1
Пример выходных данных для приведённого выше примера входных данных:
K = 2
M = 3
A = (−12, 1)
R = 1
Примечание.
Считайте, что во входных данных имеется хотя бы одна точка, не лежащая на осях координат.
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Ox, а две оставшиеся – по разные стороны от оси Ox.
Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 10 пар координат.
Напишите программу для решения такой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу – 2 балла.
Задание Б. Имеется набор данных, состоящий из пар координат. Пар может быть много.
Напишите программу для решения этой задачи.Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных.
В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки.
Описание выходных данных.
Программа должна вывести одно число — максимальную площадь четырёхгольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль.
Пример входных данных:
6
0 0
2 0
0 2
3 -3
5 -5
6 6
Пример выходных данных для приведённого выше примера входных данных:
11
Рассматривайте только четырёхугольники со сторонами лежащими не на оси Ox.
Комментарий.
В оригинальной формулировке задачи последнего условия нет, что создаёт дополнительные трудности при поиске необходимых четырёхугольников.
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Oy, а две оставшиеся — по разные стороны от оси Oy.
Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных.
В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки.
Описание выходных данных.
Программа должна вывести одно число — максимальную площадь четырёхугольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль.
Пример входных данных:
6
0 0
2 0
0 2
3 −3
−5 −5
6 6
Пример выходных данных для приведённого выше примера входных данных:
11
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости задано множество точек с целочисленными координатами. Необходимо найти максимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных: 48.
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом ринадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных: 48
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости задано множество точек с целочисленными координатами. Необходимо найти количество отрезков, обладающих следующими свойствами:
1) оба конца отрезка принадлежат заданному множеству;
2) ни один конец отрезка не лежит на осях координат;
3) отрезок пересекается ровно с одной осью координат.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N — количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа x и y — координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10 000; –1000 ≤ x, y ≤ 1000.
Пример входных данных:
4
6 6
-8 8
-9 -9
7 -5
Выходные данные
Необходимо вывести единственное число: количество удовлетворяющих требованиям отрезков.
Пример выходных данных для приведённого выше примера входных данных: 4.
Загрузка решений доступна для зарегистрировавшихся пользователей
На плоскости задано множество точек с целочисленными координатами. Необходимо найти количество отрезков, обладающих следующими свойствами:
1) оба конца отрезка принадлежат заданному множеству;
2) ни один конец отрезка не лежит на осях координат;
3) отрезок пересекается с обеими осями координат.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y — координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10000; –1000 ≤ x, y ≤ 1000.
Пример входных данных:
4
6 6
-8 8
-9 -9
7 -5
Выходные данные
Необходимо вывести единственное число: количество удовлетворяющих требованиям отрезков.
Пример выходных данных для приведённого выше примера входных данных: 2.
Загрузка решений доступна для зарегистрировавшихся пользователей