279 - Triangle

  • 데구킹
    데구킹

    왜 W/A가 나오는지 알수가 없어서 생각도 정리할 겸 한번 글을 써봅니다;

    문제에서 주어주는 3개의 좌표점을 pt[0], pt[1], pt[2] 라고 하면
    1. pt[0] ~ pt[1] , pt[1]~pt[2] , pt[2]~pt[0] 으로부터 각각 직선의 방정식 3개를 구할수가 있습니다
    2. 각 세점의 x좌표들은 삼각형을 구성하기 때문에 양 끝점과 중간점으로 구분할수 있습니다
    (중간점이 끝점중 하나와 겹칠수도 있지만 논외로 두겠습니다, 코드에서는 기울기에 1e10을 써서 없는 직선 취급합니다)
    3. 양 끝점으로 만들어진 직선의방정식 선상 위에 있는 정수의 x로부터 y값을 얻어내어 x를 인덱스로 배열에 기록해둡니다
    4. 방금 사용한 x값을 이용해서 나머지 두개의 직선의 방정식 선상위의 y값도 얻어내어 같은 방법으로 기록해둡니다
    5. 3번과 4번에서 저장해둔 배열에 저장된 값들을 각각 빼봄으로써 하나의 선상에서의 존재가능한 좌표를 얻어낼 수 있습니다

    하나의 x좌표에서 이끌어낸 두개의 y좌표 K와 L을 고려해보겠습니다 ( K < L )
    가능한 모든 경우에 있어서 두개의 실수 사이에 존재하는 정수의 개수는 다음의 수식으로 구할 수 있습니다
    cnt = floor(K+1) - ceil(L-1) + 1
    위와같은 단계를 거쳐서 코딩하여 제출해보았는데 계속 W/A가 나오네요 ;
    어디 잘못된 점이 있는지를 잘 모르겠습니다; 풀이에 오류가 존재하는지 막코딩으로 인한 코딩실수인지 ...
    아래에는 코드를 첨부합니다
    좀 지저분하네요 제가 코딩이 미숙해서 -_-;
    코드 하이라이트 이건 우쨰쓰는건지 ;;

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

    13년 전
2개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    실수문제에 따른 오차가 있으실거같네요.
    정수좌표의 점에 관한 문제라면 Pick's theorem을 참고해주세요 :)


    13년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    실제로는 정수 10인데 double로 처리하다보면 9.99999998나 10.00000001 이런 식으로 계산되는 경우를 볼 수 있죠. 아주 작은 epsilon 값을 이용해 정수인지 판별을 해보는 것도 한가지 방법이겠죠.


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