sum of area 문제에 대해서

  • YiMaeTal
    YiMaeTal

    두개의 랜덤 사각형의 넓이를 구하는 문제인데
    저는 문제를 풀때 사각형의 양 꼭지점의 위치를 가지고 네 좌표를 비교해가며 더하고 마지막에 교차하는부분이 있다면 그부분을 빼는식으로 문제를 풀었었습니다.
    이게 너무 노가다식으로 푼거같아서 여러분의 의견을 듣고싶은데요

    http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=422&sca=50&sfl=wr_subject&stx=%EB%A9%B4%EC%A0%81&sop=and

    예를들어 이런 문제라고 한다면 (저는 사각형 두개의 좌표 8개를 받아서 푸는 문제였지만)
    어떤식으로 다가가실지 궁금합니다.

    시간복잡도의 경우 O(1) 을 지키면서 풀었으면합니다.

    감사합니다^_^


    2년 전
7개의 댓글이 있습니다.
  • YiMaeTal
    YiMaeTal

    많은 댓글 부탁드립니다 :)


    2년 전 link
  • 일루
    일루

    https://www.quora.com/What-is-coordinate-compression 같은것을 알아보세요. O(1)은 힘들 것 같습니다.


    2년 전 link
  • YiMaeTal
    YiMaeTal

    @일루 역시 조건을 줘서 그냥 노가다로 하는 방법말고는 O(1) 힘든가요


    2년 전 link
  • 일루
    일루

    n이 커지면 노가다로 해도 O(1) 이 아니겠죠...


    2년 전 link
  • YiMaeTal
    YiMaeTal

    @일루 아 제 문제는 두개의 사각형이었어요.. ㅎㅎㅎ 당연 저문제에서는 O(n) 이죠 ㅎㅎ:)


    2년 전 link
  • kriii
    kriii

    어떻게 O(n)으로 할 수 있는지 잘 모르겠네요.
    두 직시각형은 각 차원에 대해 따로 보시면 비교적 깔끔하게 됩니다.


    2년 전 link
  • kiyomi
    kiyomi

    @YiMae Tal 저 죄송한데 Graph Connectivity소스좀 받을수있을까요?


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