На плоскости задано множество точек с целочисленными координатами, никакие две из которых не совпадают и никакие три не лежат на одной прямой. Необходимо найти количество треугольников, обладающих следующими свойствами:
1) все вершины треугольника принадлежат заданному множеству;
2) ни одна вершина не лежит на осях координат;
3) треугольник не пересекается с осью Oy, но пересекается с осью Ox.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y – координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10000, –1000 ≤ x, y ≤ 1000, никакие две точки не совпадают, никакие три не лежат на одной прямой.
Пример входных данных:
4
6 6
−8 8
−9 −9
−7 5
Выходные данные
Необходимо вывести единственное число: количество удовлетворяющих требованиям треугольников.
Пример выходных данных для приведённого выше примера входных данных:
1
Чтобы треугольник не пересекался с осью 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.
Пример правильной, но неэффективной программы на языке Паскаль.
beginreadln(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.