2
\$\begingroup\$

This is a C++ program that rotates a point initially located at origin by a given angle A (degree) counterclockwise and L translate its x-coordinate (sum L to it).

Here is my program:

Firstly it reads the number of test cases. Each test case has 2 real numbers and 1 integer that represents a rotation, translation and how many times the operation of rotate and translate must be applied.

#include <cstdio>
#include <utility>
#include <cmath>


#define gc getchar_unlocked()
inline double getDouble() {
    double v;
    scanf("%lf",&v);
    return v;
}

#define CONST 0.01745329251994329576922 //3.14159265358979323846/180 = 0.01745329251994329576922
std::pair<double, double> rotate(std::pair<double, double> p, double a){
    double rad = a*CONST;
    return std::make_pair(p.first*std::cos(rad) - p.second*std::sin(rad), p.first*std::sin(rad) + p.second*std::cos(rad));
}


int main(void){
    int t = (int) getDouble();

    for (int i = 0; i < t; ++i) {
        double a = getDouble(),l = getDouble();
        int v = (int) getDouble();

        std::pair<double, double> p(0,0);
        while (v--) {
            p = rotate(p, a);
            p.first += l;
         }
        //for cases like 30 1.5 121... the printf just put -0.00
        if(std::abs(p.first) < 0.005)
            p.first = 0;
        if(std::abs(p.second) < 0.005)
            p.second = 0;
        printf("%.2lf %.2lf\n",p.first,p.second);
    }

    return 0;
}

Sample input:

4
90 10 1
90 10 2
90 10 3
30 1.5 1000000000

Sample output:

10.00 0.00
10.00 10.00
0.00 10.00
3.55 3.55

How to make it faster ?

\$\endgroup\$
3
\$\begingroup\$
  • CONST is not a name; it doesn't convey any meaning. Call it something like rads_per_degree. If you feel you need to comment on the value, better do the calculation explicitly (take advantage of \$\pi\$ being defined for you in cmath):

    const double rads_per_degree = M_PI / 180;
    
  • Each time you rotate, you recalculate radian measure, sin and cos. Within the test case these values do not change. You may safely precompute them:

    double rads = rads_per_degree * angle;
    double sin = std::sin(rads);
    double cos = std::cos(rads);
    while (v--) {
        do_math(x, y, sin, cos, L);
    }
    
  • I am not sure why you special cased small values.

  • getDouble is somewhat dubious. It would've make sense to have such a function to sanitize input. As written, it is meaningless. Also, you should not read integer as double.

\$\endgroup\$
1
\$\begingroup\$

Style/Maintainability

  • You should always prefer the const keyword to a #define. This is because #define is a preprocessing statement that will do a blanket substitution of the value. This means that if you have a compile-time error in your code, you will see the # rather than your name for the number, which makes debugging much more difficult.
  • Why not template your rotate function so that it can take int points and other arithmetic types to rotate? This would be a minimal change to make your function more flexible overall.
  • No user prompt to go along with your scanf? Maybe you should use argv and just have your program take a command line argument when you start it?
  • You need comments explaining what your functions do, and probably more descriptive function names. getDouble is a particularly bad function name because double is quite a generic word as is get.
  • No need to return 0 as this is done automatically nowadays.

Efficiency

  • If you expect your users to do the same rotations repeatedly, you might consider using a map to store values you've already computed. Combine this with @vnp's suggestion to turn sin and cos into parameters for the function.

Error checking

  • You should check values after you read them in to make sure you got what you want. I don't see any error checking in getDouble
\$\endgroup\$
1
\$\begingroup\$

Firstly generate a matrix T that represents the rotation and translation for the values given.

Matrix

Here xt means the translation on x-coordinate value. yt is always 0 because there is no translation y-coordinate. Theta means the angle to rotate.

After that just do T'= T^v where v is the number of times that the operation of rotation and translation must be executed. T^v can be solved using exponentiation by squaring.

Finally multiply a vector 3x1 with values x y 1 (where x and y means the initial point in this case 0 0) representing the point with T'. The resulting vector of the multiplication has the answer.

The overall complexity of this solution is O(log(n)). Better than this O(n) solution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.