WATERWORLD 문제. 틀릴만한 부분이 없는데 틀리다고 나오네요..

  • iyaa
    iyaa

    https://algospot.com/judge/problem/read/WATERWORLD

    로직 설명입니다.

    1. 입력받은후 사면체중 최대의 넓이를 가진 면 (삼각형)을 찾습니다.

    2. 6개의 모서리를 삼각형에 포함된 모서리와, 아닌 모서리로 구분합니다.

    3. 6개의 모서리의 길이를 이용, 사면체의 부피를 구합니다.
      부피는 아래의 공식으로 구하였습니다.
      https://en.wikipedia.org/wiki/Tetrahedron#Heron-type_formula_for_the_volume_of_a_tetrahedron

    4. 이분법을 이용하여 답을 구해나갑니다.
      (물을 붓고, 사면체에서 늘어난 부피만큼 계산하고 그걸 다시 부은걸로 셈하는 방식)

    물론 디버깅용 cout등등은 다 처리하였고..
    로직 자체에 문제가 있는것 같지는 않습니다.
    어디가 문제인지... 고수분들 답변주시면 감사하겠습니다.

    아래는 소스입니다.

    #define _CRT_SECURE_NO_WARNINGS
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<sstream>
    #include<string>
    #include<vector>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<fstream>
    #include<cassert>
    #include<numeric>
    #include<set>
    #include<map>
    #include<queue>
    #include<list>
    #include<deque>
    #include<stack>
    #define INF 987654321
    using namespace std;
    double heron(double a, double b, double c){
        return (sqrt((4 * a*a*b*b) - ((a*a + b*b - c*c)*(a*a + b*b - c*c)))) / 4;
    }
    double volume(vector<double>& tri, vector<double>& other){
        double U = tri[0];
        double V = tri[1];
        double W = tri[2];
        double u = other[0];
        double v = other[1];
        double w = other[2];
    
        double X = (w - U + v)*(U + v + w);
        double x = (U - v + w)*(v - w + U);
        double Y = (u - V + w)*(V + w + u);
        double y = (V - w + u)*(w - u + V);
        double Z = (v - W + u)*(W + u + v);
        double z = (W - u + v)*(u - v + W);
        double a = sqrt(x*Y*Z);
        double b = sqrt(y*Z*X);
        double c = sqrt(z*X*Y);
        double d = sqrt(x*y*z);
    
        double vol = sqrt((-a + b + c + d)*(a - b + c + d)*(a + b - c + d)*(a + b + c - d)) / (192 * u*v*w);
        return vol;
    }
    double height(double tri, double vol){
        double ret = vol * 3;
        ret /= tri;
        return ret;
    }
    double solve(double trianglearea, double triheight, double g, double h){
        double _trianglearea = trianglearea;
        double _triheight = triheight;
        double _g = g;
        double _h = h;
        double area = g*g;
        double ret = 0;
        double nextheight = min(_h, _triheight);
        cout << endl;
        for (int i = 0; i < 200; i++){
            double vol1 = area*nextheight;
            double vol2 = (_trianglearea*nextheight)/3.0;
            nextheight = vol2 / area;
            _trianglearea = (nextheight*trianglearea) / triheight;
            cout << vol1 << " " << vol2 << " " << nextheight << " " << _trianglearea << endl;
            ret += nextheight;
        }
        return ret;
    }
    
    
    int main(){
        int T;
        cin >> T;
        while (T--){
            double g, h;
            cin >> g >> h;
            double a, b, c, d, e, f;
            cin >> a >> b >> c >> d >> e >> f;
            //abc
            //ade
            //bef
            //cdf
            double mmax = 0;
            vector<double> tri(3);
            vector<double> other(3);
            if (mmax < heron(a, b, c)){ 
            mmax = max(mmax, heron(a, b, c)); 
            tri[0] = a;
            tri[1] = b;
            tri[2] = c;
            other[0] = d;
            other[1] = e;
            other[2] = f;
            }
            if (mmax < heron(a, d, e)){ mmax = max(mmax, heron(a, d, e)); 
            tri[0] = a;
            tri[1] = d;
            tri[2] = e;
            other[0] = b;
            other[1] = c;
            other[2] = f;
            }
            if (mmax < heron(b, e, f)){ mmax = max(mmax, heron(b, e, f)); 
            tri[0] = b;
            tri[1] = e;
            tri[2] = f;
            other[0] = a;
            other[1] = c;
            other[2] = d;
            }
            if (mmax < heron(c, d, f)){ mmax = max(mmax, heron(c, d, f)); 
            tri[0] = c;
            tri[1] = d;
            tri[2] = f;
            other[0] = a;
            other[1] = b;
            other[2] = e;
            }
            double vol = volume(tri, other);
            double hei = height(mmax, vol);
            //cout << mmax << " "<< volume(tri, other) << " "<<hei<<endl;
            printf("%.3lf\n", solve(mmax, hei, g, h));
            //cout<<solve(mmax, hei, g, h) << endl;
    
        }
        system("pause");
    }
    


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