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


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

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

1) оба конца отрезка принадлежат заданному множеству;

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

3) отрезок пересекается с обеими осями координат.

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

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

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

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

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

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

4

6 6

-8 8

-9 -9

7 -5

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

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

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

Решение.

Отрезок, концы которого не лежат на осях координат, пересекается с обеими осями координат в том и только в том случае, если его концы лежат в противоположных четвертях. Если известны величины n1, n2, n3, n4, показывающие количество точек в каждой четверти, то количество отрезков равно n1n3 + n2n4.

Эффективная программа решения задачи подсчитывает количество точек по четвертям и вычисляет ответ по вышеприведённой формуле.

Ниже приводится такая программа на языках Паскаль и Java.

 

Пример правильной программы на Паскале

 

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*n3 + n2*n4;

writeln(s)

end.

 

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

 

import java.util.Scanner;

public class P27B {

  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 > 0) { n1++ ; }

      if (x < 0 && y > 0) { n2++ ; }

      if (x < 0 && y < 0) { n3++ ; }

      if (x > 0 && y < 0) { n4++ ; }

    }

    int s = n1*n3 + n2*n4;

    System.out.println(s);

  }

}

 

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

var

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

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

s: integer; {количество отрезков}

i, j: integer;

begin

readln(N);

for i := 1 to N do read(a[i, 1], a[i, 2]);

for i := 1 to N do

for j := 1 to N do begin

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

s := s + 1;

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

s := s + 1;

end;

writeln(s);

end.


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