겨울 캠프 기하 파트 H번 질문 있습니다.

  • 로제폰
    로제폰

    문제가 무엇이 틀렸는지 알기 힘들었는데 이 문제가 탑코더에 있어서 거기서 틀린 샘플을 보면서
    탑코더에서 System Test를 통과했습니다. 그리고 아주대 온라인저지에 맞춰 입출력을 변경하고 제출했는데
    WrongAnswer가 뜹니다. 더 까다로운 input값을 가진 것인지 아니면 input값이 잘못됬는지 모르겠습니다. 탑코더의 다른 분 소스 중 하나도 온라인저지에 제출해봤는데 WA가 떴습니다.

    아주대 온라인 저지 아이디가 lozephon입니다. 다음은 제 소스입니다.

    PS. 이거 소스 올리면 바로 소스 보이는데 여기서 접기 태그 어떻게 사용하는지 아시나요;; 잘 안되네요
    소스 보기

    #include<stdio.h>
    #include<math.h>
    #include<limits.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    struct Point {
      double x, y;
    };
    
    struct Line {
      Point st, ed;
      double slope;
    
      Line() {};
      Line(Point _st, Point _ed) {
        st = _st; ed = _ed;
        slope = getSlope(st, ed);
      };
    
      double getSlope(Point st, Point ed) {
        return (ed.y-st.y)/(ed.x-st.x);
      };
    
      double getHeight(double x) {
        return slope*(x-st.x)+st.y;
      };
    
      void print() {
        printf("st : %lf %lf ed : %lf %lf slope : %lf\n", st.x, st.y, ed.x, ed.y, slope);
      };
    };
    
    Point getCrossPoint(double a, double b, double c, double p, double q, double r) {
      Point cp;
      cp.x = (c*q-r*b)/(b*p-a*q);
      cp.y = (a*r-c*p)/(b*p-a*q);
      return cp;
    }
    
    Point getCrossPoint(Line a, Line b) {
      Point cp;
      if(a.slope - b.slope < 1e-9) {
        cp.x = a.ed.x;
        cp.y = a.ed.y;
      }
      else {
        cp.x = (a.st.y-a.slope*a.st.x+b.slope*b.st.x-b.st.y)/(b.slope-a.slope);
        cp.y = (a.slope*(b.slope*b.st.x-b.st.y)-b.slope*(a.slope*a.st.x-a.st.y))/(b.slope-a.slope);
      }
    
      return cp;
    }
    
    
    int main() {
      //  freopen("input.in", "r", stdin);
    
      int t;
      scanf("%d", &t);
    
      while(t--) {
        int n;
        scanf("%d", &n);
    
        vector<double> position(n);
        vector<Point> ps(n);
        for(int i = 0;i<n;i++) {
          scanf("%lf", &ps[i].x);
          position[i] = ps[i].x;
        }
        for(int i = 0;i<n;i++)
          scanf("%lf", &ps[i].y);    
    
        for(int i = 0;i<n;i++)
          Line tempLine(ps[i], ps[i+1]);
    
        Point maxCP = {ps[1].x, ps[1].y};
        double ans = (double)0x7fffffff;
        bool isMax = false;
        for(int i = 0;i<n-1;i++) {
          Line leftLine(ps[i], ps[i+1]);
          for(int j = i+1;j<n-1;j++) {
            Line rightLine(ps[j], ps[j+1]);
            if(leftLine.slope * rightLine.slope > -1e-9)
              continue;
            Point cp = getCrossPoint(leftLine, rightLine);
    
            if(maxCP.y < cp.y) {
              maxCP = cp;
              isMax = true;
            }
          }
        }
    
        if(isMax) {
          int idx = lower_bound(position.begin(), position.end(), maxCP.x) - position.begin();
          Line middleLine(ps[idx-1], ps[idx]);
          ans = maxCP.y-middleLine.getHeight(maxCP.x);
        }
    
        for(int i = 0;i<n;i++) {
          double posHeight = 0.0;
          for(int j = 0;j<n-1;j++) {
            Line line(ps[j], ps[j+1]);
            double tempHeight = line.getHeight(ps[i].x) - ps[i].y;
            if(tempHeight > posHeight)
              posHeight = tempHeight;
          }
          if(ans > posHeight)
            ans = posHeight;
        }
    
        printf("%.3lf\n", ans);
      }
    }
    

    9년 전
8개의 댓글이 있습니다.
  • 김우현
    김우현

    1
    6
    1 2 3 4 6 7
    0 1 0 2 4 4

    Expected Result = 1.0 입니다.
    로제폰님 프로그램으로는 결과가 2.0이 나오네요.

    상당히 시간 복잡도가 좋은 효율적인 프로그램이라 좀 꼼꼼히 분석해 봤습니다.
    86번째 줄에서 가정으로 기울기의 부호가 반대인 경우에 대해서만 교점을 확인하는데요.
    반례로 주어진 입력은 기울기가 같은 두 직선의 교점이 해가 되는 예제 입니다.

    결론. 너란 systest.... 못난 systest....

    PS. 헤헤 시테 통과하셨다니 챌린지 하러 가겠습니다 +_+!ㅋㅋ


    9년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    음.. 근데.. 제 솔루션도 WA가 뜨네요. 뭔가 문제가 있긴 있는 것 같아요. :(


    9년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    채점 데이터에 문제가 있는 것으로 확인되었습니다. 설 지나고 수정될 예정입니다. 제출이 무지 많은데..ㅠㅠ 죄송합니다..


    9년 전 link
  • 로제폰
    로제폰

    김우현 //
    그런 경우가 있었군요..감사합니다. 덕분에 코드를 수정하였습니다. 기울기 부호가 반대의 경우를 빼고서 j = i+1이 아니라 i+2부터 돌리고(바로 옆 선분과는 붙어있으므로) 교점의 x값이 pos[0]와 pos[n-1]을 벗어나지 않는 값만 체크하게 하였습니다. 알려주신 경우와 Systemtest는 통과하네요. 더이상 문제가 없기를 ㅜㅜ

        for(int i = 0;i<n-1;i++) {
          Line leftLine(ps[i], ps[i+1]);
          for(int j = i+2;j<n-1;j++) {
            Line rightLine(ps[j], ps[j+1]);
            Point cp = getCrossPoint(leftLine, rightLine);
    
            if(maxCP.y < cp.y && cp.x > ps[0].x-1e-9 && cp.x < ps[n-1].x+1e-9) {
              maxCP = cp;
              isMax = true;
            }
          }
        }
    

    Taeyoon_Lee //
    괜찮습니다. 제출횟수는 신경 안 쓴지 오래고 윗분이 알려주셨듯 틀린 경우가 있었으니까요;;..설 끝나면 제출해봐야겠네요. 답변 감사합니다.


    9년 전 link
  • 로제폰
    로제폰

    ...실수로 댓글 두개 달았는데 댓글은 지울수 없나요;


    9년 전 link
  • 김우현
    김우현

    http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3073
    확실하게 확인하시려면 위 사이트에서도 확인해 보는 것도 좋을 것 같습니다.
    같은 문제 인데, N제한이 1000입니다.


    9년 전 link
  • hyunhwan
    hyunhwan

    안녕하세요. lavida운영자 리베입니다.
    확인 결과 다음의 두가지 문제가 있었고 이를 해결하였습니다.
    1. 출력데이터 오류
    2. 부동 소수점 자료형 출력시 발생하는 오차, 이 부분은 special judge가 가능하여 오차 범위가 10^-3 이내일 경우 정답으로 간주하게 하였습니다.

    위의 문제릉 해결한 다음 1635번에 대한 모든 제출을 재채점 하였으니 확인바랍니다.


    9년 전 link
  • wody34
    wody34

    으억 채점 데이터에 문제가 있긴 했군요ㅜㅜ

    저도 같이 풀었었는데 재채점 AC 나왔네요 ^^


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