Необходимо найти количество отрезков, обладающих следующими свойствами
Условие
На плоскости задано множество точек с целочисленными координатами. Необходимо найти количество отрезков, обладающих следующими свойствами:1) оба конца отрезка принадлежат заданному множеству;2) ни один конец отрезка не лежит на осях координат;3) отрезок пересекается ровно с одной осью координат.Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.Входные данныеВ первой строке задаётся N — количество точек в заданном множестве.Каждая из следующих строк содержит два целых числа x и y — координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10 000; -1000 ≤ x, y ≤ 1000.Пример входных данных:46 6-8 8-9 -97 -5Выходные данныеНеобходимо вывести единственное число: количество удовлетворяющих требованиям отрезков.Пример выходных данных для приведённого выше примера входных данных: 4. Критерии оценивания выполнения задания | Баллы | Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве. Программа удовлетворяет требованиям эффективности, указанным в условии задачи.Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). | 4 | Не выполнены условия, позволяющие поставить 4 балла, при этом программа работает верно, время работы линейно зависит от N, но размер используемой памяти зависит от количества точек.Например, входные данные запоминаются в массиве или другой структуре данных, размер которой соответствует числу N.Допускается одна из следующих ошибок.1. Пропущенная или неверная инициализация максимумов.2. В некоторых языках и системах программирования (например, в Бейсике) все переменные после создания имеют значение 0. В этом случае отсутствие инициализации нельзя считать ошибкой.3. Вместо абсолютных значений (модулей) используются непосредственные значения координат.4. Ошибка в сравнении, в результате которой в одном или нескольких местах находится минимальное значение вместо максимального.5. Использование вещественных вычислений и операции извлечения корня для нахождения площади.6. Неверная обработка случая отсутствия требуемого треугольника. Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла. | 3 | Не выполнены условия, позволяющие поставить 3 или 4 балла, приэтом программа работает верно, эффективно или нет. В частности, в 2 балла оцениваются переборные решения, в которых все исходные данные сохраняются в массиве, рассматриваются все возможные треугольники, из которых выбираются подходящие. Допускается наличие нескольких содержательных ошибок, описанных в критериях на 3 балла, и до пяти синтаксических ошибок, описанных в критериях на 4 балла. | 2 | Не выполнены условия, позволяющие поставить 2, 3 или 4 балла, но программа работает в отдельных частных случаях. 1 балл также ставится, если программа неработоспособна или не написана, но из пояснений видно, что экзаменуемый в целом верно представляет путь решения. | 1 | Не выполнены условия, позволяющие поставить 1, 2, 3 или 4 балла. | 0 | Максимальный балл | 4 |
Формат задания
Решение по шагам
Как рассуждать
Решение. Отрезок, концы которого не лежат на осях координат, пересекается ровно с одной осью в том и только в том случае, если его концы лежат в соседних четвертях. Если известны величины n₁, n₂, n₃, n₄, показывающие количество точек в каждой четверти, то количество отрезков равно n₁n₂ + n₂n₃ + n₃n₄ + n₄n₁.Упростив это выражение, получим (n₁ + n₃)(n₂ + n₄).Это выражение можно получить и непосредственно из условий задачи, если обратить внимание на то, что у каждого подходящего отрезка один конец лежит в нечётной четверти, а другой — в чётной и для определения количества отрезков можно считать точки не в каждой четверти отдельно, а их общее количество в чётных и нечётных четвертях.Оба подхода (подсчёт по каждой четверти отдельно и по двум группам) позволяют получить эффективные программы. Ниже приводятся программы на языках Паскаль и Java для обоих способов. Пример правильной программы на Паскале program P27; var N: integer; {количество точек} x,y: integer; {координаты очередной точки} n1, n2: integer; {количество точек по чётным и нечётным четвертям} s: integer; {количество отрезков} i: integer;begin readln(N); n1:=0; n2:=0; for i:=1 to N do begin readln(x,y); if xy > 0 then n1:=n1+1; if xy < 0 then n2:=n2+1; {нельзя ставить else - возможны нули} end; s := n1*n2; writeln(s)end. Пример правильной и эффективной программы на языке Java (подсчёт по каждой четверти отдельно) import java.util.Scanner;public class P27A2 { public static void main(String args[]) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int n1 = 0, n2 = 0, n3 = 0, n4 = 0; for (int i=0; i < N; ++i) { int x = in.nextInt(); int y = in.nextInt(); if (x > 0 && y >
Осталось ещё 4 шага
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Бесплатно · займёт минуту