РЕШУ ЕГЭ — информатика

Задания

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

1)  все вершины треугольника принадлежат заданному множеству;

2)  ни одна вершина не лежит на осях координат;

3)  треугольник не пересекается с осью Oy, но пересекается с осью Ox.

Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.

Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

Входные данные

В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y – координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10000, –1000 ≤ x, y ≤ 1000, никакие две точки не совпадают, никакие три не лежат на одной прямой.

Пример входных данных:

6 6

−8 8

−9 −9

−7 5

Выходные данные

Необходимо вывести единственное число: количество удовлетворяющих требованиям треугольников.

Пример выходных данных для приведённого выше примера входных данных:

Решение. Чтобы треугольник не пересекался с осью Oy и пересекался с осью Ox, его вершины должны лежать в одной полуплоскости относительно Oy и в разных относительно Ox. Получается, что вершины треугольника должны лежать

в первой и четвёртой либо во второй и третьей четвертях, причём в одной из этих четвертей должны лежать две вершины, в другой  — одна.

Зная количество точек в каждой четверти, можно подсчитать количество искомых треугольников. Например, если в первой четверти лежит n1 точек, а в четвёртой – n4 точек, то количество треугольников, у которых две вершины лежат в первой четверти, а одна  — в четвёртой, равно (n1(n1–1)/2) * n4 = n1(n1–1)n4/2.

Если известны величины n1, n2, n3, n4, показывающие количество точек в каждой четверти, то общее количество треугольников равно (n1(n1-1)n4 + n4(n4-1)n1 + n2(n2-1)n3 + n3(n3-1)n2) / 2.

Пример правильной и эффективной программы на языке Паскаль

program P27;

  var

    N: integer; {количество точек}

    x,y: integer; {координаты очередной точки}

    n1, n2, n3, n4: integer;

      {количество точек по четвертям}

    s: integer; {количество треугольников}

    i: integer;

begin

  readln(N);

  n1:=0; n2:=0; n3:=0; n4:=0;

  for i:=1 to N do begin

    readln(x,y);

    if (x>0) and (y>0) then n1 := n1+1;

    if (x<0) and (y>0) then n2 := n2+1;

    if (x<0) and (y<0) then n3 := n3+1;

    if (x>0) and (y<0) then n4 := n4+1;

  end;

  s := (n1*n4*(n1+n4-2) + n2*n3*(n2+n3-2)) div 2;

  writeln(s)

end.

Пример правильной, но неэффективной программы на языке Паскаль.

begin  readln(N);
  s := 0;
  for i := 1 to N do read(a[i, 1], a[i, 2]);
  for i := 1 to N do
    for j := i+1 to N do
      for k := j+1 to N do
        if (a[k, 1]<0) and (a[j, 1]<0) and (a[i, 1]<0) then begin
          if ((a[k, 2]<0) and (a[j, 2]>0)) or ((a[k, 2]<0) and (a[i, 2]>0)) or ((a[k, 2]<0) and (a[j, 2]>0)) then
            s := s + 1;
          if ((a[k, 2]>0) and (a[j, 2]<0)) or ((a[k, 2]>0) and (a[i, 2]<0)) or ((a[k, 2]>0) and (a[j, 2]<0)) then
            s := s + 1;
        end;
        if (a[k, 1]>0) and (a[j, 1]>0) and (a[i, 1]>0) then begin
          if ((a[k, 2]<0) and (a[j, 2]>0)) or ((a[k, 2]<0) and (a[i, 2]>0)) or ((a[k, 2]<0) and (a[j, 2]>0)) then
            s := s + 1;
          if ((a[k, 2]>0) and (a[j, 2]<0)) or ((a[k, 2]>0) and (a[i, 2]<0)) or ((a[k, 2]>0) and (a[j, 2]<0)) then
            s := s + 1;
        end;
  writeln(s);
end.

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку).	4
Не выполнены условия, позволяющие поставить 4 балла, при этом программа работает верно, время работы линейно зависит от N, но размер используемой памяти зависит от количества точек. Например, входные данные запоминаются в массиве или другой структуре данных, размер которой соответствует числу N. Допускается одна из следующих ошибок. 1. Пропущенная или неверная инициализация количества точек. В некоторых языках и системах программирования (например, в Бейсике) все переменные после создания имеют значение 0. В этом случае отсутствие инициализации нельзя считать ошибкой. 2. Неверные сравнения, в результате которых учитываются точки, лежащие на осях координат. 3. Учёт одного треугольника несколько раз из-за разной последовательности перечисления вершин (например, отсутствие деления на 2 в решении, аналогичном приведённому выше). 4. Учёт треугольников, содержащих одну и ту же вершину дважды (например, отсутствие вычитания в решении, аналогичном приведённому выше). Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла, при этом программа работает верно, эффективно или нет. В частности, в 2 балла оцениваются переборные решения, в которых все исходные данные сохраняются в массиве, рассматриваются все возможные треугольники, из которых выбираются подходящие. Допускается наличие нескольких содержательных ошибок, описанных в критериях на 3 балла, и до пяти синтаксических ошибок, описанных в критериях на 4 балла.	2
ННе выполнены условия, позволяющие поставить 2, 3 или 4 балла, но программа работает в отдельных частных случаях.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Ключ