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

  • User Avatar
    로제폰

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

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

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

    #include
    #include
    #include
    #include
    #include
    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);

    }
    }


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

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

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

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

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

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


    15년 전 link
  • User Avatar
    Taeyoon_Lee

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


    15년 전 link
  • User Avatar
    Taeyoon_Lee

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


    15년 전 link
  • User Avatar
    로제폰

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

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

    15년 전 link
  • User Avatar
    로제폰

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


    15년 전 link
  • User Avatar
    김우현

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


    15년 전 link
  • User Avatar
    hyunhwan

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

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


    15년 전 link
  • User Avatar
    wody34

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

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


    15년 전 link

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