От­ре­зок, концы ко­то­ро­го не лежат на осях ко­ор­ди­нат, пе­ре­се­ка­ет­ся с обе­и­ми осями ко­ор­ди­нат в том и толь­ко в том слу­чае, если его концы лежат в про­ти­во­по­лож­ных чет­вер­тях. Если из­вест­ны ве­ли­чи­ны n₁, n₂, n₃, n₄, по­ка­зы­ва­ю­щие ко­ли­че­ство точек в каж­дой чет­вер­ти, то ко­ли­че­ство от­рез­ков равно n₁n₃ + n₂n₄.

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

Ниже при­во­дит­ся такая про­грам­ма на язы­ках Пас­каль и 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.

От­ре­зок, концы ко­то­ро­го не лежат на осях ко­ор­ди­нат, пе­ре­се­ка­ет­ся ровно с одной осью в том и толь­ко в том слу­чае, если его концы лежат в со­сед­них чет­вер­тях. Если из­вест­ны ве­ли­чи­ны n₁, n₂, n₃, n₄, по­ка­зы­ва­ю­щие ко­ли­че­ство точек в каж­дой чет­вер­ти, то ко­ли­че­ство от­рез­ков равно n₁n₂ + n₂n₃ + n₃n₄ + n₄n₁.

Упро­стив это вы­ра­же­ние, по­лу­чим (n₁ + n₃)(n₂ + n₄).

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

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

  }

}