이런 문제는 어떻게 풀수있을까요..?

  • hyida
    hyida


    n개 사각형의 좌표가 주어지는데 이 때 사각형이 겹쳐서생기는 모든 다각형의 개수를 구하고 다각형들의 넓이 중 가장 큰 것의 넓이를 구하는 문제입니다..
    이 때 생기는 다각형의 개수는 1,000,000개 이하이고 n은 50000 이하라고 주어집니다.. n개의 사각형은 x축,y축에 평행합니다..
    n^2 플레인스위핑을 인덱스트리 사용해서 n lg n만드는식인거 같은데
    어떤식으로 플레인스위핑 해야될지 잘 모르겠네요..
    도와주시면 감사하겟습니다..ㅜㅜ

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    10년 전
11개의 댓글이 있습니다.
  • Yongrok
    Yongrok

    n개 사각형이 겹쳐서 다각형이 만들어 진다는 건가요...!?!?


    10년 전 link
  • walsub
    walsub

    n개의 사각형이 x축 y축에 평행하다는 조건이있나요? KOI 기출문제와 매우 유사하네요..


    10년 전 link
  • hyida
    hyida

    아 죄송합니다.. n개의 사각형이 x축,y축에 평행하다는 조건이 있구요.. n개 사각형이 겹쳐서 다각형이 만들어지는거에요....ㅠ;;


    10년 전 link
  • nocut98
    nocut98

    지금 그림은 사각형 하나랑 팔각형 하나가 있는 건가요?


    10년 전 link
  • hyida
    hyida

    사각형 5개가 겹쳐서 7개의 다각형이 나오는데, 저기 색칠된 넓이가 가장 큰 다각형의 넓이입니다..


    10년 전 link
  • ipknHama
    ipknHama

    hole이 있어도 되는건가요?


    10년 전 link
  • hyida
    hyida

    1 네..


    10년 전 link
  • ltdtl
    ltdtl

    방법 ) SNU의 hp^3팀에게 던져주고 회신을 기다립니다.


    10년 전 link
  • Kureyo
    Kureyo

    n제한이 얼마인가요?


    10년 전 link
  • wookayin
    wookayin
    • n : 50,000 (n^2 gg), k (영역의 수) : 1,000,000간단히 생각해봤는데 제가 떠올린 방법의 기본 idea는 x방향으로 플레인 스위핑을 하면서 y축에 평행한 segment [y1, y2] 하나가 그려질 때 새로운 영역이 생기고, 하나가 빠질 때 그 영역이 끝난다는 식으로 영역들을 maintain 하는데 얘네들이 하나의 영역으로 합쳐진다는 걸(?) Union and Find 와 유사한 방식으로 관리한다...는 느낌입니다.n^2 는 그럭저럭 짤 수 있겠지만 n lgn 은 어렵죠. 따라서 Segment Tree 나 Interval Tree 를 써서 해결할 수 있을 듯 합니다. 이게 k가 n^2 가 아니고 백만정도기 때문에 가능한 풀이인 것 같은데.. (머릿속으로만ㅁㄴㅇㄹ) 시험기간이니(?) 시험이 끝난후에 자세하게 풀어봐야겠네요 ㅎㅎ

    10년 전 link
  • Dynamical
    Dynamical

    일단 점들이 모두 많아야 200만개정도 나올거 같은데, 그냥 단순히 각각의 조각들에 대해서 sweep 하는걸로 안될까요


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.