ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1793. Tray 2

Notes to authors of this problem.
Posted by 198808xc 31 Aug 2011 21:45
In fact, it cost me 4 submissions to get accepted. However, I still think that this is a problem with simple geometry. However, some confusion in the problem statement rather made a big trouble for me.

The problem statement said that the plates had the shape of truncated cones. However, it still remains a problem, that which bottom of the truncated cone is larger. By the common sense, the upper bottom of the cone should be larger, and it is indeed so in the testdata (I have submitted a checker for this), but the fact does not appear in the statements.
PS: even if the lower bottom is larger, my program could still give the correct results.

Secondly, the height of the tray need NOT be larger than (or equal with) the height of the cones. If the height of tray is smaller, the plates could still fit in the tray, and in this situation, some part of the plates could even be outside the tray. So important the condition is, it doesn't appear in the problem statements at all! I could not understand this.

And, at last, I want to give the last hint to all authors: try to solve this problem by 64-bit integers. Floating point numbers might bring in errors, which you don't want to see.
Re: Notes to authors of this problem.
Posted by Sandro (USU) 31 Aug 2011 22:12
Oops! Of course, the radius of plate's edge is greater than the radius of plate's bottom.
I have fixed the problem statement.
Re: Notes to authors of this problem.
Posted by 198808xc 31 Aug 2011 22:55
Well, I think that correcting the second confusion could be more important.

Or, is this an intentional trap of this problem?
Re: Notes to authors of this problem.
Posted by IgorKoval(from Pskov) 1 Sep 2011 03:03
It's good idea to use 64-bit fractional arithmetic.

#include <iostream>
#include <algorithm>
using namespace std;

__int64 gcd( __int64 a, __int64 b ) {
    return b? gcd( b, a%b ) : a ;
}

class drobT {
    public :
        __int64 u, d;
        drobT()
        {
            u = 0;
            d = 1;
        }
        friend drobT socr ( drobT a ) {
            __int64 div, x, y;
            x = (a.u>=0)? a.u : -1*a.u;
            y = (a.d>=0)? a.d : -1*a.d;
            div = gcd( max(x,y), min(x,y) );
            a.u /= div;
            a.d /= div;
            return a;
        }
        friend drobT operator  + ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.d + b.u * a.d;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator  - ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.d - b.u * a.d;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator * ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.u;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator * ( const __int64& a, const drobT& b )
        {
            drobT c;
            c.u = a * b.u;
            c.d = b.d;
            return socr(c);
        }
        friend drobT operator  / ( const drobT& a, const drobT& b )
        {
            drobT c = b;
            if( c.u < 0 ) {
                c.u = -c.u;
                c.d = -c.d;
            }
            swap( c.d, c.u );
            return socr(c * a);
        }
        friend bool operator <= ( drobT a, drobT b ) { return a.u*b.d <= a.d*b.u;}
        friend bool operator <= ( const __int64 a, drobT b ) { return a*b.d <= b.u;}
        friend bool operator < ( drobT a, drobT b ) { return a.u*b.d < a.d*b.u; }
        friend bool operator < ( const __int64 num, drobT b ) { return num*b.d < b.u; }
        friend drobT pow2( const drobT& a ){ return a*a; }
};
//input
istream& operator >> ( istream& cin, drobT& dr  ) {
    cin >> dr.u;
    dr.d = 1;
    return cin;
}

/*
secret code)
*/
Re: Notes to authors of this problem.
Posted by 198808xc 1 Sep 2011 19:42
Wow, it's a good template for double-precision calculations.
However, this problem could be solved with single-precision __int64 numbers.