СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Cайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 11256

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

 

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

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

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

 

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

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

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

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

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

 

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

4

6 6

−8 8

−9 −9

7 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) / 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*n2*(n1+n2-2) + n3*n4*(n3+n4-2)) div 2;

  writeln(s)

end.

 

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

var

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

a: array[1..10000, 1..2] of integer; {исходные данные}

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

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

i, j, k: integer;

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 begin

if (a[k, 2]<0) and (a[j, 2]<0) and (a[i, 2]<0) then begin

if ((a[k, 1]<0) and (a[j, 1]>0)) or ((a[k, 1]<0) and (a[i, 1]>0)) or ((a[k, 1]<0) and (a[j, 1]>0)) then

s := s + 1;

if ((a[k, 1]>0) and (a[j, 1]<0)) or ((a[k, 1]>0) and (a[i, 1]<0)) or ((a[k, 1]>0) and (a[j, 1]<0)) then

s := s + 1;

end;

if (a[k, 2]>0) and (a[j, 2]>0) and (a[i, 2]>0) then begin

if ((a[k, 1]<0) and (a[j, 1]>0)) or ((a[k, 1]<0) and (a[i, 1]>0)) or ((a[k, 1]<0) and (a[j, 1]>0)) then

s := s + 1;

if ((a[k, 1]>0) and (a[j, 1]<0)) or ((a[k, 1]>0) and (a[i, 1]<0)) or ((a[k, 1]>0) and (a[j, 1]<0)) then

s := s + 1;

end;

end;

writeln(s);

end.


Аналоги к заданию № 11256: 11283 Все