Необходимо найти количество треугольников, обладающих следующими
Условие
На плоскости задано множество точек с целочисленными координатами, никакие две из которых не совпадают и никакие три не лежат на одной прямой. Необходимо найти количество треугольников, обладающих следующими свойствами:
- все вершины треугольника принадлежат заданному множеству;2) ни одна вершина не лежит на осях координат;3) треугольник не пересекается с осью Ox, но пересекается с осью Oy. Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данныеВ первой строке задаётся N - количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y - координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10000, -1000 ≤ x, y ≤ 1000, никакие две точки не совпадают, никакие три не лежат на одной прямой. Пример входных данных:46 6−8 8−9 −97 5 Выходные данныеНеобходимо вывести единственное число: количество удовлетворяющих требованиям треугольников. Пример выходных данных для приведённого выше примера входных данных:1
Формат задания
Решение по шагам
Как рассуждать
Решение. Чтобы треугольник не пересекался с осью Ox и пересекался с осью Oy, его вершины должны лежать в одной полуплоскости относительно Ox и в разных относительно Oy. Получается, что вершины треугольника должны лежать в первой и второй либо в третьей и четвёртой четвертях, причём в одной из этих четвертей должны лежать две вершины, в другой — одна.
Зная количество точек в каждой четверти, можно подсчитать количество искомых треугольников. Например, если в первой четверти лежит n1 точек, а во второй — n2 точек, то количество треугольников, у которых две вершины лежат в первой четверти, а одна - во второй, равно (n1(n1-1)/2) * n2 = n1(n1-1)n2/2.Если известны величины n1, n2, n3, n4, показывающие количество точек в каждой четверти, то общее количество треугольников равно (n1(n1-1)n2 + n2(n2-1)n1 + n3(n3-1)n4 + n4(n4-1)n3) /
Осталось ещё 1 шаг
Пример правильной и эффективной программы на…
Бесплатно · займёт минуту