겨울 캠프 기하 파트 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);
  }
}

    13년 전
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. 헤헤 시테 통과하셨다니 챌린지 하러 가겠습니다 +_+!ㅋㅋ


    13년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

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


    13년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

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


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


    13년 전 link
  • 로제폰
    로제폰

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


    13년 전 link
  • 김우현
    김우현

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


    13년 전 link
  • hyunhwan
    hyunhwan

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

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


    13년 전 link
  • wody34
    wody34

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

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


    13년 전 link

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