logo

TechCodeview

매우 정확한

수평선과 수직선 사이의 삼각형 수 찾기

전제 조건: 조금  주어진 'n'개의 선분은 각각 수평이거나 수직입니다. 선분의 교차점을 연결하여 형성할 수 있는 삼각형(면적이 0인 삼각형 포함)의 최대 수를 구하십시오. 두 개의 수평선 세그먼트가 겹치지 않으며 두 개의 수직선 세그먼트도 겹치지 않습니다. 선은 두 개의 점을 사용하여 표현됩니다(첫 번째 두 개의 정수는 각각 첫 번째 점의 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가지 이벤트를 설명하겠습니다.
      ~에 - 수평선 부분의 가장 왼쪽 지점 밖으로 - 수평선 부분의 가장 오른쪽 지점
    • 에이 수직선
  3. 우리는 지역에 전화를 겁니다. '활동적인' 아니면 수평선 '활동적인' 첫 번째 이벤트는 있었지만 두 번째 이벤트는 발생하지 않았습니다. 모든 활성 라인의 'y' 좌표를 저장하는 BIT(Binary indexed tree)가 있습니다.
  4. 라인이 비활성화되면 BIT에서 'y'를 제거합니다.
  5. 세 번째 유형의 이벤트가 발생하면, 즉 수직선에 있을 때 'y' 좌표 범위의 트리를 쿼리하고 그 결과를 지금까지의 교차점 수에 추가합니다.
  6. 마지막으로 우리는 교차점의 수를 말하게 될 것입니다. 중 그러면 삼각형의 수(영 영역 포함)는 다음과 같습니다. 중 기음 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


공유하다

마음에 드실지도 몰라요

어떤 하드웨어 장치 드라이버를 업데이트해야 합니까?

어떤 하드웨어 장치 드라이버를 업데이트해야 합니까?

예제와 함께 Java의 asList() 메소드 배열

예제와 함께 Java의 asList() 메소드 배열

인기 기사

범주

블로그 자바 변환 수학 자바 컬렉션 차이점 자바 문자열

재미있는 기사