logo

TechCodeview

数学的

水平線分と垂直線分の中から三角形の数を求める

前提条件: 少し  'n' 個の線分が水平または垂直である場合、線分の交点を結合することによって形成できる三角形 (面積がゼロの三角形を含む) の最大数を求めます。 2 つの水平線分は重なりませんし、2 つの垂直線分も重なりません。線は 2 つの点を使用して表されます (4 つの整数のうち、最初の 2 つはそれぞれ最初の点の x 座標と y 座標であり、他の 2 つは 2 番目の点の 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 つのイベントを説明してみましょう。
      で - 水平線分の左端の点 外 - 水平線分の右端の点
    • ある 縦線
  3. 私たちはその地域をこう呼んでいます 'アクティブ' または水平線 'アクティブ' 最初のイベントはあったが、2 番目のイベントはなかった。すべてのアクティブなラインの 'y' 座標を保存するための BIT (バイナリ インデックス ツリー) を用意します。
  4. ラインが非アクティブになると、その「y」を BIT から削除します。
  5. 3 番目のタイプのイベントが発生するとき、つまり垂直線にいるとき、「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)


共有

あなたにおすすめ

機械学習における遺伝的アルゴリズム

機械学習における遺伝的アルゴリズム

ニューヨーク市立大学ベスト6の学校とその素晴らしさ

ニューヨーク市立大学ベスト6の学校とその素晴らしさ

トップ記事

カテゴリ

ブログ Java変換 数学 Java コレクション 違い Java文字列

興味深い記事