319 - Pendulum

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

319 - Pendulum

Post by junbin » Thu Feb 05, 2004 4:02 pm

I'm trying to solve q319 Pendulum and I keep getting WA..

The program works for all my test data, but I can't really be sure if they'll fulfil the judge's requirements.

Can anyone be kind enough to answer these questions?

1) Are the hooks ALL on INTEGER coordinates? (ie: (3, 4) and NOT (3.441, 2.33), etc. )

2) Do we need a special formatting function before outputting the results? I know for some questions, using printf("%.2llf"); will give WA because of rounding errors.. so does this question require any special rounding functions?

3) distance moved by the pedulum in a arc of teeta radians when it's length is l is equal to teeta * l. Is this forumla correct or is there a more precise one?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Thu Feb 05, 2004 8:48 pm

1) I don't know. My solution doesn't gain anything by treating them as integers, so I store and read them as doubles.

2) No. I use printf("... %.2f ...",...);

3) I shouldn't think so.

Some I/O:

Code: Select all

8 100
0 -51
0 -50
5 1
-5 2
6 100
0 1
0 2
1 0
0 5000000
3 20
5 -5
10 -10
8 -2
4 40
-10 -20
-10 -10
-9 -21
-9 -18
1 20
0 -5
0 0
Output (numbering wrong since I skipped sample I/O):

Code: Select all

Pendulum #3
Length of periodic orbit = 6.28

Pendulum #4
Length of periodic orbit = 31415926.54

Pendulum #5
Length of periodic orbit = 36.81

Pendulum #6
Length of periodic orbit = 21.25

Pendulum #7
Length of periodic orbit = 120.15

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sat Feb 07, 2004 5:03 am

My code gives the same results... but still WA.

Can I just check with you your parameters?
I use the following:

typedef long double ft;
#define EPS 1e-15
#define pi 3.14159265358979



Basically, I use long double to store all my hooks' coordinates and all floating point operations are in long double. Precision is to 1e-15 and pi is taken as 3.14159265358979.

From experience, I find that for floating point questions, being too precise (or too imprecise) will lead to WA.. can you give me the parameters you are using? Thank you!

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sat Feb 07, 2004 1:23 pm

I use

const double pi = 2.0*acos(0.0);

for pi, which IMO is better than using a numerical constant. For epsilon, I have 1e-7.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sat Feb 07, 2004 6:43 pm

Per wrote:I use

const double pi = 2.0*acos(0.0);

for pi, which IMO is better than using a numerical constant. For epsilon, I have 1e-7.
Thank you for your help.. I've managed to get AC'ed..

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 319 - Pendulum

Post by metaphysis » Fri Jun 02, 2017 6:29 pm

Test data generator:

Code: Select all

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <map>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    int cases = 1000, x1, y1;
    for (int c = 1; c <= cases; c++)
    {
        int n = rand() % 100;
        int lengthOfString = rand() % 10000 + 1;
        
        cout << n << ' ' << lengthOfString << '\n';
        
        map<int, map<int, bool>> cache;
        cache[0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            do
            {
                x1 = rand() % 100;
                if (rand() % 2 == 0) x1 *= -1;
                y1 = rand() % 100;
                y1 *= -1;
            } while (cache.find(x1) != cache.end() && cache[x1].find(y1) != cache[x1].end());
            
            cout << x1 << ' ' << y1 << '\n';
            cache[x1][y1] = true;
        }
    }
    
    cout << "0 0\n";
    return 0;
}

Post Reply

Return to “Volume 3 (300-399)”