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


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

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

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

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

3) отрезок пересекается ровно с одной осью координат.

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

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

В первой строке задаётся N — количество точек в заданном множестве.

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

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

4

6 6

-8 8

-9 -9

7 -5

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

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

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

Решение.

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

Упростив это выражение, получим (n1 + n3)(n2 + n4).

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

Оба подхода (подсчёт по каждой четверти отдельно и по двум группам) позволяют получить эффективные программы. Ниже приводятся программы на языках Паскаль и 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 x*y > 0 then n1:=n1+1;

    if x*y < 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 > 0) { n1++ ; }

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

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

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

    }

    int s = n1*n2 + n2*n3 + n3*n4 + n4*n1;

    System.out.println(s);

  }

}


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