427 - FlatLand Piano Movers

[Saranga]

I used trigonometry and derivative to calculate the maximum excursion of the piano into the corridor and if this value is less than the width it prints "Y", otherwise "N". In the test cases of course it works, and in drawings I have made it seems to work also. I have tried moving to next test case immediately on "N" or continuing, and both WA.

Any sample inputs or reasons why my program is getting WA? I can find no problem with it.

[Saranga]

Ah I had bad math. There is no way to take the derivative and get a simple formula. I got accepted by iterating thorugh angles and checking them.

[metaphysis]

Use ternary search. The code below is test data generator.

Code: Select all

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

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));

    for (int c = 1; c <= 100; c++)
    {
        int l = rand() % 1000;
        int w = rand() % 1000;
        
        if (l < w) swap(l, w);
        if (l == w) l += 25;
        
        cout << l << ',' << w;
        
        for (int i = 1; i <= 20; i++)
        {
            cout << ' ';
            
            int corner = w + rand() % 1000 + 1;
            cout << corner << ',';
            corner = w + rand() % 1000 + 1;
            cout << corner;
        }
        cout << '\n';
    }

    return 0;
}