logo

TechCodeview

Математичний

Знаходження кількості трикутників між горизонтальними та вертикальними відрізками

Передумови: БІТ  Дано 'n' відрізків, кожен з яких горизонтальний або вертикальний. Знайдіть максимальну кількість трикутників (включаючи трикутники з нульовою площею), які можна утворити шляхом з'єднання точок перетину відрізків. Ні два горизонтальні відрізки не перекриваються, ні два вертикальні відрізки не перекриваються. Лінія представлена ​​за допомогою двох точок (чотири цілі числа, перші два з яких є координатами x і y відповідно для першої точки, а інші два є координатами x і y для другої точки) приклади: 

 | ---|-------|-- | | ----- | --|--|- | | | | For the above line segments there are four points of intersection between vertical and horizontal lines every three out of which form a triangle so there can be    4C   3     triangles.

Ідея заснована на Алгоритм розгортки лінії . Поетапне створення рішення:

  1. Збережіть обидві точки всіх відрізків лінії з відповідною подією (описаною нижче) у векторі та відсортуйте всі точки в порядку неспадання їхніх координат x.
  2. Давайте тепер уявімо вертикальну лінію, яку ми проводимо через усі ці точки, і опишемо 3 події, виходячи з того, в якій точці ми зараз:
      в - крайня ліва точка горизонтального відрізка поза - крайня права точка горизонтального відрізка
    • a вертикальна лінія
  3. Називаємо область "активний" або горизонтальні лінії "активний" які мали першу подію, але не другу. У нас буде BIT (двійкове індексоване дерево) для зберігання координат «y» усіх активних ліній.
  4. Коли рядок стає неактивним, ми видаляємо його 'y' з BIT.
  5. Коли відбувається подія третього типу, тобто коли ми перебуваємо на вертикальній лінії, ми запитуємо дерево в діапазоні його координат «y» і додаємо результат до кількості точок перетину на даний момент.
  6. Нарешті ми матимемо кількість точок перетину м тоді кількість трикутників (включаючи нульову площу) буде м C 3 .

Примітка: Нам потрібно ретельно відсортувати точки, подивитися на cmp() функцію в реалізації для пояснення. 

CPP 
   // A C++ implementation of the above idea   #include     #define maxy 1000005   #define maxn 10005   using     namespace     std  ;   // structure to store point   struct     point   {      int     x       y  ;      point  (  int     a       int     b  )      {      x     =     a       y     =     b  ;      }   };   // Note: Global arrays are initially zero   // array to store BIT and vector to store   // the points and their corresponding event number   // in the second field of the pair   int     bit  [  maxy  ];   vector  &  lt  ;  pair  &  lt  ;  point       int  &  gt  ;     &  gt  ;     events  ;   // compare function to sort in order of non-decreasing   // x coordinate and if x coordinates are same then   // order on the basis of events on the points   bool     cmp  (  pair  &  lt  ;  point       int  &  gt  ;     &  amp  ;  a       pair  &  lt  ;  point       int  &  gt  ;     &  amp  ;  b  )   {      if     (     a  .  first  .  x     !=     b  .  first  .  x     )      return     a  .  first  .  x     &  lt  ;     b  .  first  .  x  ;      //if the x coordinates are same      else      {      // both points are of the same vertical line      if     (  a  .  second     ==     3     &  amp  ;  &  amp  ;     b  .  second     ==     3  )      {      return     true  ;      }      // if an 'in' event occurs before 'vertical'      // line event for the same x coordinate      else     if     (  a  .  second     ==     1     &  amp  ;  &  amp  ;     b  .  second     ==     3  )      {      return     true  ;      }      // if a 'vertical' line comes before an 'in'      // event for the same x coordinate swap them      else     if     (  a  .  second     ==     3     &  amp  ;  &  amp  ;     b  .  second     ==     1  )      {      return     false  ;      }      // if an 'out' event occurs before a 'vertical'      // line event for the same x coordinate swap.      else     if     (  a  .  second     ==     2     &  amp  ;  &  amp  ;     b  .  second     ==     3  )      {      return     false  ;      }      //in all other situations      return     true  ;      }   }   // update(y 1) inserts a horizontal line at y coordinate   // in an active region while update(y -1) removes it   void     update  (  int     idx       int     val  )   {      while     (  idx     &  lt  ;     maxn  )      {      bit  [  idx  ]     +=     val  ;      idx     +=     idx     &  amp  ;     (  -  idx  );      }   }   // returns the number of lines in active region whose y   // coordinate is between 1 and idx   int     query  (  int     idx  )   {      int     res     =     0  ;      while     (  idx     &  gt  ;     0  )      {      res     +=     bit  [  idx  ];      idx     -=     idx     &  amp  ;     (  -  idx  );      }      return     res  ;   }   // inserts a line segment   void     insertLine  (  point     a       point     b  )   {      // if it is a horizontal line      if     (  a  .  y     ==     b  .  y  )      {      int     beg     =     min  (  a  .  x       b  .  x  );      int     end     =     max  (  a  .  x       b  .  x  );      // the second field in the pair is the event number      events  .  push_back  (  make_pair  (  point  (  beg       a  .  y  )     1  ));      events  .  push_back  (  make_pair  (  point  (  end       a  .  y  )     2  ));      }      //if it is a vertical line      else      {      int     up     =     max  (  b  .  y       a  .  y  );      int     low     =     min  (  b  .  y       a  .  y  );      //the second field of the pair is the event number      events  .  push_back  (  make_pair  (  point  (  a  .  x       up  )     3  ));      events  .  push_back  (  make_pair  (  point  (  a  .  x       low  )     3  ));      }   }   // returns the number of intersection points between all   // the lines vertical and horizontal to be run after the   // points have been sorted using the cmp() function   int     findIntersectionPoints  ()   {      int     intersection_pts     =     0  ;      for     (  int     i     =     0     ;     i     &  lt  ;     events  .  size  ()     ;     i  ++  )      {      //if the current point is on an 'in' event      if     (  events  [  i  ].  second     ==     1  )      {      //insert the 'y' coordinate in the active region      update  (  events  [  i  ].  first  .  y       1  );      }      // if current point is on an 'out' event      else     if     (  events  [  i  ].  second     ==     2  )      {      // remove the 'y' coordinate from the active region      update  (  events  [  i  ].  first  .  y       -1  );      }      // if the current point is on a 'vertical' line      else      {      // find the range to be queried      int     low     =     events  [  i  ++  ].  first  .  y  ;      int     up     =     events  [  i  ].  first  .  y  ;      intersection_pts     +=     query  (  up  )     -     query  (  low  );      }      }      return     intersection_pts  ;   }   // returns (intersection_pts)C3   int     findNumberOfTriangles  ()   {      int     pts     =     findIntersectionPoints  ();      if     (     pts     &  gt  ;  =     3     )      return     (     pts     *     (  pts     -     1  )     *     (  pts     -     2  )     )     /     6  ;      else      return     0  ;   }   // driver code   int     main  ()   {      insertLine  (  point  (  2       1  )     point  (  2       9  ));      insertLine  (  point  (  1       7  )     point  (  6       7  ));      insertLine  (  point  (  5       2  )     point  (  5       8  ));      insertLine  (  point  (  3       4  )     point  (  6       4  ));      insertLine  (  point  (  4       3  )     point  (  4       5  ));      insertLine  (  point  (  7       6  )     point  (  9       6  ));      insertLine  (  point  (  8       2  )     point  (  8       5  ));      // sort the points based on x coordinate      // and event they are on      sort  (  events  .  begin  ()     events  .  end  ()     cmp  );      cout     &  lt  ;  &  lt  ;     &  quot  ;  Number     of     triangles     are  :     &  quot  ;     &  lt  ;  &  lt  ;      findNumberOfTriangles  ()     &  lt  ;  &  lt  ;     &  quot  ;    n  &  quot  ;;      return     0  ;   }

Вихід: 

Number of triangles are: 4 
Time Complexity:   O( n * log(n) + n * log(maximum_y) )

Допоміжний простір: O(maxy), де maxy = 1000005


Поділитися

Вам Може Сподобатися

Що таке повна форма JBL

Що таке повна форма JBL

Правило PEMDAS: розуміння порядку операцій

Правило PEMDAS: розуміння порядку операцій

Кращі Статті

Категорія

Блог Перетворення Java Математика Колекції Java Відмінності Рядок Java

Цікаві Статті