seoul regional 2008 E번 Archery 질문입니다..

  • xesmaster
    xesmaster

    알고리즘이 맞는거 같은데 live archive에서 계속 WA를 뱉어내서
    힘드네요..ㅠㅠ

    https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2254

    일단 알고리즘은 모든 페어마다 엑스자로 y=0과 만나는 구간을 생성해서 이러한 페어마다의 구간(n^2개)의 교집합이 있는지 없는지를 체크하는 알고리즘인데요..

    맞는 알고리즘인거같은데 계속 틀리네요. 기본적으로 n^2으로 걍 돌리면 TLE가 나오길래 도중에 커팅 코드를 집어넣엇는데 아무래도 double 타입 오차범위때문에 이러는거같은데 고칠수가 없네요 ㅠㅠ 유리수로 해봤는데 생각해보니x절편 구할때 분모에 10^14정도까지 올라가서 비교함수에서 곱셈 연산에서 overflow가 나서 long long타입으로 유리수를 줘도 안되고.. gcd로 분모분자 낮추는 코드를 집어넣으면 TLE가 나고.. 그렇다고 bignum으로 하자니 또 TLE 날꺼같고 ㅠㅠ 도와주세요..

    #define EPS 1e-9
    
    struct Line {
        int y,x1,x2;
        Line(){}
        Line(int a, int b, int c) : y(a), x1(b), x2(c) {}
        bool operator < (const Line &a) const {
            return y < a.y;
        }
    } L[5005];
    
    int T,n,W;
    
    double calc(double x1, double y1, double x2, double y2) {
        double A = y1 - y2;
        double B = x2 - x1;
        double C = -(A*x1+B*y1);
        return -C / A;
    }
    
    int main() {
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&W,&n);
            for(int i=0;i<n;++i) {
                int y,x1,x2; scanf("%d%d%d",&y,&x1,&x2);
                L[i] = Line(y,x1,x2);
            } sort(L, L + n);
    
            double s = 0, e = W;
            for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) {
                s = max(s,calc(L[i].x1,L[i].y,L[j].x2,L[j].y));
                e = min(e,calc(L[i].x2,L[i].y,L[j].x1,L[j].y));
                if(s - EPS> e) break;
            }
            if(s - EPS > e) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
    }
    


    10년 전
2개의 댓글이 있습니다.
  • Apple_Cplus
    Apple_Cplus

    계산식 잘못된게 아닐까여? calc 바꾸니 맞네여
    return x1-(double)y1*(x2-x1)/(y2-y1);


    10년 전 link
  • xesmaster
    xesmaster

    헐 calc 저부분은 직선방정식 ax+by+c=0으로 표현하는 거 Petr코드 닌자해온건데.. 뭐지 ㅠㅠ


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