Найти количество помех

@Norwand · Регистрация: 18.12.2017

Author24 — интернет-сервис помощи студентам

Помогите пожалуйста решить задачу, ну или хотя бы ее идею, у самой не получается, а хотелось бы разобраться
Условие :

Кликните здесь для просмотра всего текста

Во время проектирования Ксиопо (компьютера, позволяющего определить местоположение любой антены на Земле) Ксавьер столкнулся со следующей проблемой. Задача поиска всех антен одновременно чрезвычайно сложна. Каждая антена обладает своей силой, и каждая антена наводит некоторые помехи, мешающие поиску. Если представить Землю плоской (при поиске в ограниченной области это разумное допущение), то и каждую антену, и Ксиопо можно представить точкой на плоскости. Каждая тройка антен, такая, что Ксиопо находится строго внутри треугольника, образованного этими антенами, добавляет одну единицу помех. Если Ксиопо находится вне или на границе такого треугольника, помехи не возникают. Таким образом, суммарное число помех — сумма помех по всем тройкам антен. Помогите Ксавьеру найти это число.
Формат ввода
В первой строке входного файла записано одно целое число n (3 ≤ n ≤ 105) — число антен.

Во второй строке входного файла записана пара целых чисел x, y (-109 ≤ x, y ≤ 109) — координаты Ксиопо.

В следующих n строках записаны пары чисел xi, yi (-109 ≤ xi, yi ≤ 109) — координаты антен.

Известно, что координаты всех точек в условии (и антен, и Ксиопо) различны.
Формат вывода
В единственной строке выходного файла выведите искомое число помех.

Тесты :

1 тест

Кликните здесь для просмотра всего текста

Ввод :
6
0 0
1 1
-1 1
1 -1
-1 -1
2 0
0 2
Вывод
3

2 тест

Кликните здесь для просмотра всего текста

Ввод :
3
0 0
0 1
-1 -1
1 -1
Вывод
1

@woldemas · 27.12.2017, 14:49

Ну базовая идея - перебрать все тройки и проверить сколько треугольников содержит внутри точку с координатами Ксиопо. Это и будет величина помех. Это если в лоб, может как-то оптимизировать перебор можно.

@Norwand · 27.12.2017, 15:28 **[ТС]**

То есть, считать все тройки в двумерный массив, и потом перебором проверять входит ли точка в тройку?
Или Вы что то другое имеете ввиду?

~~Остап Бонд~~ · 27.12.2017, 18:34

Потестите -

C#

using System;
 
namespace PR5
{
  class MainClass
  {
    public static int S(int ax, int ay, int bx, int by, int cx, int cy)
    {
      return (ax - cx) * (by - cy) - (bx - cx) * (ay - cy);
    }
    public static void Main(string[] args)
    {
      int n = 6, p = 0;
      int x = 0, y = 0;
      int[] ax = { 1, -1, 1, -1, 2, 0 };
      int[] ay = { 1, 1, -1, -1, 0, 2 };
      //int n = 3, p = 0;
      //int x = 0, y = -1;
      //int[] ax = { 0, -1, 1 };
      //int[] ay = { 1, -1, -1 };
      for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
          for (int k = j + 1; k < n; k++)
          {
            int s1 = S(x, y, ax[i], ay[i], ax[j], ay[j]);
            int s2 = S(x, y, ax[j], ay[j], ax[k], ay[k]);
            int s3 = S(x, y, ax[k], ay[k], ax[i], ay[i]);
            if (s1 * s2 > 0 && s2 * s3 > 0 && s3 * s1 > 0)
              p++;
          }
      Console.WriteLine(p);
      Console.ReadLine();
    }
  }
}

Если всё правильно, со чтением файлов поразбирайтесь сами - мы этого ещё не проходили

@Norwand · 27.12.2017, 22:19 **[ТС]**

Сообщение от Остап Бонд

Потестите -

C#

using System;
 
namespace PR5
{
  class MainClass
  {
    public static int S(int ax, int ay, int bx, int by, int cx, int cy)
    {
      return (ax - cx) * (by - cy) - (bx - cx) * (ay - cy);
    }
    public static void Main(string[] args)
    {
      int n = 6, p = 0;
      int x = 0, y = 0;
      int[] ax = { 1, -1, 1, -1, 2, 0 };
      int[] ay = { 1, 1, -1, -1, 0, 2 };
      //int n = 3, p = 0;
      //int x = 0, y = -1;
      //int[] ax = { 0, -1, 1 };
      //int[] ay = { 1, -1, -1 };
      for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
          for (int k = j + 1; k < n; k++)
          {
            int s1 = S(x, y, ax[i], ay[i], ax[j], ay[j]);
            int s2 = S(x, y, ax[j], ay[j], ax[k], ay[k]);
            int s3 = S(x, y, ax[k], ay[k], ax[i], ay[i]);
            if (s1 * s2 > 0 && s2 * s3 > 0 && s3 * s1 > 0)
              p++;
          }
      Console.WriteLine(p);
      Console.ReadLine();
    }
  }
}

Если всё правильно, со чтением файлов поразбирайтесь сами - мы этого ещё не проходили

Не совсем поняла, зачем два массива для координат антент?Если у нас будет 10^5 антен, нам придеться создавать столько же массивов?Можно объяснить этот момент пожалуйста.

~~Остап Бонд~~ · 27.12.2017, 22:32

Norwand, один массив с координатами X, второй - Y.
Рано вам, похоже, за такие задачки браться...

@Norwand 0 / 0 / 0 Регистрация: 18.12.2017 Сообщений: 4
		1
	Найти количество помех 27.12.2017, 14:11. Показов 466. Ответов 5 Метки нет (Все метки) Помогите пожалуйста решить задачу, ну или хотя бы ее идею, у самой не получается, а хотелось бы разобраться Условие : Кликните здесь для просмотра всего текста Во время проектирования Ксиопо (компьютера, позволяющего определить местоположение любой антены на Земле) Ксавьер столкнулся со следующей проблемой. Задача поиска всех антен одновременно чрезвычайно сложна. Каждая антена обладает своей силой, и каждая антена наводит некоторые помехи, мешающие поиску. Если представить Землю плоской (при поиске в ограниченной области это разумное допущение), то и каждую антену, и Ксиопо можно представить точкой на плоскости. Каждая тройка антен, такая, что Ксиопо находится строго внутри треугольника, образованного этими антенами, добавляет одну единицу помех. Если Ксиопо находится вне или на границе такого треугольника, помехи не возникают. Таким образом, суммарное число помех — сумма помех по всем тройкам антен. Помогите Ксавьеру найти это число. Формат ввода В первой строке входного файла записано одно целое число n (3 ≤ n ≤ 105) — число антен. Во второй строке входного файла записана пара целых чисел x, y (-109 ≤ x, y ≤ 109) — координаты Ксиопо. В следующих n строках записаны пары чисел xi, yi (-109 ≤ xi, yi ≤ 109) — координаты антен. Известно, что координаты всех точек в условии (и антен, и Ксиопо) различны. Формат вывода В единственной строке выходного файла выведите искомое число помех. Тесты : 1 тест Кликните здесь для просмотра всего текста Ввод : 6 0 0 1 1 -1 1 1 -1 -1 -1 2 0 0 2 Вывод 3 2 тест Кликните здесь для просмотра всего текста Ввод : 3 0 0 0 1 -1 -1 1 -1 Вывод 1 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	27.12.2017, 14:49	2
	Ну базовая идея - перебрать все тройки и проверить сколько треугольников содержит внутри точку с координатами Ксиопо. Это и будет величина помех. Это если в лоб, может как-то оптимизировать перебор можно. 0

@Norwand 0 / 0 / 0 Регистрация: 18.12.2017 Сообщений: 4
	27.12.2017, 15:28 [ТС]	3
	То есть, считать все тройки в двумерный массив, и потом перебором проверять входит ли точка в тройку? Или Вы что то другое имеете ввиду? 0

~~Остап Бонд~~ Заблокирован
	27.12.2017, 22:32	6
	Norwand, один массив с координатами X, второй - Y. Рано вам, похоже, за такие задачки браться... 0