TOYOFJAEHA 제가 놓친 게 있을까요ㅠ.ㅠ..

  • restart
    restart

    재하의 장난감를 풀고 있는데요, 계속된 WA에 알고리즘상 문제인지 알고 싶어서 질문합니다ㅠ

    문제를 간단히 설명하자면 3\le N\le100개의 점이 주어지고, P_{i}P_{i+1}…, P_NP_1을 이어서 생기는 면적 0이상의 내부공간을 세는 문젠데요..

    간단히 선분 교점들로 이루어진 planar graph를 구성하고 Euler's formula를 적용하면 될 것 같은데 구현상에 애로사항이 꽃피네요..

    제 알고리즘은 다음과 같습니다.

    1. 각 선분쌍을 순회하며 교점들의 set을 유지한다.
    2. 각 선분을 순회하면서, (x좌표, 같으면 y좌표로 정렬된) set의 요소를 순회하며 선분상의 점을 찾고, 그 이전에 찾은 점과 함께 Edge set에 추가한다. (시작점 번호, 끝점 번호)
    3. 답은 1+e-v가 된다. e는 2에서 구한 Edge set의 size, v는 1에서 구한 교점 set의 size이다.

    1에서는 pair<double, double>의 set유지가 되는가 하는 precision문제가 있을 것 같으나.. x, y범위가 \le100이라 큰 상관은 없을 것 같은데... ㅠㅠ제가 놓친 예외가 있는 걸까요?ㅠㅠ


    5년 전
10개의 댓글이 있습니다.
  • 일루
    일루

    음 이 문제는 아무래도 구현이 힘든 문제라 ㅠㅠ

    혹시

    4
    0 0
    2 0
    1 0
    3 0

    이런거 처리 되나요?


    5년 전 link
  • restart
    restart

    0나옵니당 ㅜㅜ..


    5년 전 link
  • 일루
    일루

    일단 그 부분은 맞네요 ㅠㅠ


    5년 전 link
  • JongMan
    JongMan

    set<vector2>를 그대로 쓰시면 안되고, 중복 확인할 때 최소한 epsilon 확인이라도 하셔야 할 것 같은데요..


    5년 전 link
  • JongMan
    JongMan

    요런 코드를 넣고 돌려보니 RTE가 납니다.

            for(auto it = pset.begin(); it != pset.end(); ++it) {
                auto jt = it; 
                ++jt;
                while(jt != pset.end()) {
                    assert((*it-*jt).norm() < 1e-8);
                }
            }
        }
    

    두 개의 아주 가까운 점(아마도 같은 점으로 취급되어야 할)이 들어 있다는 얘기죠. 아무리 범위가 작아도 2의 자승꼴만 다루지 않는 이상 오류는 필연적이므로, 그냥 실수를 사용하시면 안 될 겁니다.


    5년 전 link
  • restart
    restart

    operator==연산에 EPSILON처리를 해놓고 안심했는데 set은 !comp(a,b)&&!comp(b,a)로 동일처리를 하는군요-_-; operator<와 ccw에도 EPSILON처리를 하니 AC가 나왔습니다! 범위가 작더라도 조심해야 하는군요..


    5년 전 link
  • wookayin
    wookayin

    넵, 말씀하신대로 std::set의 동등성 비교에서는 operator ==를 쓰지 않기 때문에 입실론 처리를 해주어야 합니다. 하지만 (std::set에서 요구되는) 엄밀하게는, operator < 가 지켜야 하는 strict weak ordering 성질에는 transitivity 가 있습니다. 즉, a==b이고 b==c이면 a==c여야 하는데, epsilon이 들어가면 이게 참이 아니죠. 그래서 std::set의 동작이 여전히 잘못될 가능성은 있습니다.

    실제로 입실론을 조절하다보면 맞을 수도 있어서 이런 케이스가 드물긴 하겠지만.. 조심해야 하는 부분이라 코멘트 남겨봅니다~


    5년 전 link
  • 일루
    일루

    넵 사실은 정수연산을 하는 것이 가장 정석적이죠!


    5년 전 link
  • restart
    restart

    다른 분 답안을 보니 homogeneous system을 쓰고 있더라구요 이참에 공부해야겠습니다ㅋㅋ부동소수점 연산은 항상 찝찝해요.. wookayin님이 말씀해주신 대로 AC받은 답안도 특정 테스트케이스에선 오답이 나올 가능성이 없다고는 할 수 없겠네요ㅠㅠ! 답글 달아 주신 모든 분들 감사합니다!


    5년 전 link
  • JongMan
    JongMan

    위 코드에서 제 assertion은 부등호 방향이 반대로 되어 있네요 ㅋㅋㅋㅋ 아놔.. 저게 틀린 점이 맞긴 맞았나 보군요 다행히 ;)


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