10개의 댓글이 있습니다.

• 
  일루

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

  혹시

  4
  0 0
  2 0
  1 0
  3 0

  이런거 처리 되나요?

  
  9년 전 link

• 
  restart

  0나옵니당 ㅜㅜ..

  
  9년 전 link

• 
  일루

  일단 그 부분은 맞네요 ㅠㅠ

  
  9년 전 link

• 
  JongMan

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

  
  9년 전 link

• 
  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의 자승꼴만 다루지 않는 이상 오류는 필연적이므로, 그냥 실수를 사용하시면 안 될 겁니다.

  
  9년 전 link

• 
  restart

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

  
  9년 전 link

• 
  wookayin

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

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

  
  9년 전 link

• 
  일루

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

  
  9년 전 link

• 
  restart

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

  
  9년 전 link

• 
  JongMan

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

  
  9년 전 link

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