# Solving for <45 degree angles of a multi-vector system

I'm working on a problem from codechef.com. The goals are:

1. Solve for whether or not the driver took a "sharp turn", meaning for some angle θ, θ > 45°.
2. Test each point $(x_i, y_i)$ in the system to see if moving one of the points to a new location $(x_j, y_j)$ such that $x_j \in [0, 50] \wedge y_j \in [0, 50]$ would cause all of the angles to subsequently be less than 45°.

I've tested the code below, and it solves the problem, but I have two primary concerns:

1. I exceed the allotted time limit
2. I use a goto in an attempt to speed up the process, which is bad practice.

#include "stdafx.h"
#include <iostream>
#include <vector>
#include<cmath>

using namespace std;

int main()
{
int t, n, i, j, k, l, m, iteration = 0, z, q=0;
double a, b, c, angle, pi = 3.1415926535897, test = 45.0000000000;
bool sharp = false, equal = false, changes = true;

cin >> t;   //Input the number of test cases
while (t--)
{
sharp = false;  //reset to "no sharp turns"

cin >> n;   //Input the number of points for this test case
vector<double> x, y, x2, y2; //x and y are the copies that do not get changes, x2 and y2 are changed and reset back to x/y
x.resize(n);
y.resize(n);

for (i = 0; i < n; ++i) //Input "n" points
{
cin >> x[i];
cin >> y[i];
}

for (i = 0; i < (n - 2); ++i)   //calculates the angle of each vertex in the system
{
a = sqrt((x[i + 1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));
b = sqrt((x[i + 2] - x[i+1])*(x[i + 2] - x[i+1]) + (y[i + 2] - y[i+1])*(y[i + 2] - y[i+1]));
c = sqrt((x[i + 2] - x[i])*(x[i + 2] - x[i]) + (y[i + 2] - y[i])*(y[i + 2] - y[i]));

//calculating the length of each side (c is not an actual side, used for the angle calculation)

angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi); //calculating the angle

if (angle > test) //if the angle is larger than "test" (45), we have a sharp turn, set to true;
{
sharp = true;
}
}

x2.resize(n);
y2.resize(n);
x2 = x;
y2 = y;     //set the values of x2 and y2 to their original values before manipulation

vector<bool> change; //testing to see if we can change all angles to <45
change.resize(n-2); //need all of the angles to be <= 45, so create an array of bools to see if all angles changes to false

for (i = 0; i < (n - 2); ++i)
{
change[i] = true;       //set to default true
}
q = 0; //q tracks if all of the values are false, if all are false then q == n -2
for (m = 0; m < n; ++m) //m is the current point we are working with, changing it
{
for (j = 0; j <= 50; ++j) //j is the current x value we are trying
for (k = 0; k <= 50; ++k) //k is the current y value we are trying
{
for (l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (j == x[l] && k == y[l])
equal = true;
}
if (!equal) //if this isn't a point we already have....
{
x2[m] = j; //set this point to j, k
y2[m] = k;

for (i = 0; i < (n - 2); ++i) // do the same math as above
{
a = sqrt((x2[i + 1] - x2[i])*(x2[i + 1] - x2[i]) + (y2[i + 1] - y2[i])*(y2[i + 1] - y2[i]));
b = sqrt((x2[i + 2] - x2[i + 1])*(x2[i + 2] - x2[i + 1]) + (y2[i + 2] - y2[i + 1])*(y2[i + 2] - y2[i + 1]));
c = sqrt((x2[i + 2] - x2[i])*(x2[i + 2] - x2[i]) + (y2[i + 2] - y2[i])*(y2[i + 2] - y2[i]));

angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi);

if (angle <= test) // if the angle is now <= 45 set this to false, then repeat to see if all angles are <=45
{
change[i] = false;

}

}

x2 = x; //reset our values
y2 = y;

for (i = 0; i < (n - 2); ++i) //test to see if all the values are false now
{
if (change[i] == false)
++q;
}
if (q == (n - 2)) //if all the values are false now, break the for loop and give the final answer for this test case
{
changes = false;
goto skip;
}
q = 0;  //reset our q
for (i = 0; i < n - 2; ++i) //reset the bool array
change[i] = true;
}

equal = false; //reset the "is equal" to false for next
}

}

skip:
if (sharp == true && changes == true)   //if there are sharp turns, and changing the points does not remove the sharp turn, no no
cout << "no no" << '\n';
else if (sharp == false)                //If there are no sharp turns, the second is automatically a yes as well, yes yes
cout << "yes yes" << '\n';
else if (sharp == true && changes == false) //if there are sharp turns, and changing the points can remove it, no yes
cout << "no yes";

changes = true; //reset changes
}

return 0;
}

• Welcome to Code Review. You would be more likely to get an answer if you included a description of what the input is, and how your solution currently works. Otherwise, this is mostly a "code dump" to be reverse-engineered. Note that MathJax is available for writing equations. – 200_success Mar 12 '18 at 22:00
• I'm assuming this is the challenge in question? – yuri Mar 12 '18 at 22:24
• Interesting that code does c = sqrt(...)  and then uses c in c*c. – chux - Reinstate Monica Mar 13 '18 at 12:36
• The problem is poorly stated. What it really apparently means is that any turn that is less than 135 degrees is a "sharp turn". – Edward Mar 13 '18 at 17:47

First easy cleanup

"stdafx.h" is not needed for your code (which is good because it is not available on my system).

Also, the indentation in your code seems wrong.

By enabling all warnings on my compiler, it tells me that iteration and z are not used. A good way not to have unused variable and to make your code easier to follow is to define variable in the smallest possible scope, at late as possible.

This also removes the need for all the "resetting" logic which is easy to get wrong. It is much easier to just define your variable and give it a meaningful initial value before using it.

At this stage, the code looks like:

// https://codereview.stackexchange.com/questions/189441/solving-for-45-degree-angles-of-a-multi-vector-system
#include <iostream>
#include <vector>
#include<cmath>

using namespace std;

int main()
{
int t;
double pi = 3.1415926535897, test = 45.0000000000;

cin >> t;   //Input the number of test cases
while (t--)
{
int n;

cin >> n;   //Input the number of points for this test case
vector<double> x, y, x2, y2; //x and y are the copies that do not get changes, x2 and y2 are changed and reset back to x/y
x.resize(n);
y.resize(n);

for (int i = 0; i < n; ++i) //Input "n" points
{
cin >> x[i];
cin >> y[i];
}

bool sharp = false;
for (int i = 0; i < (n - 2); ++i)   //calculates the angle of each vertex in the system
{
double a = sqrt((x[i + 1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));
double b = sqrt((x[i + 2] - x[i+1])*(x[i + 2] - x[i+1]) + (y[i + 2] - y[i+1])*(y[i + 2] - y[i+1]));
double c = sqrt((x[i + 2] - x[i])*(x[i + 2] - x[i]) + (y[i + 2] - y[i])*(y[i + 2] - y[i]));

//calculating the length of each side (c is not an actual side, used for the angle calculation)

double angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi); //calculating the angle

if (angle > test) //if the angle is larger than "test" (45), we have a sharp turn, set to true;
{
sharp = true;
}
}

x2.resize(n);
y2.resize(n);
x2 = x;
y2 = y;     //set the values of x2 and y2 to their original values before manipulation

vector<bool> change; //testing to see if we can change all angles to <45
change.resize(n-2); //need all of the angles to be <= 45, so create an array of bools to see if all angles changes to false

for (int i = 0; i < (n - 2); ++i)
{
change[i] = true;       //set to default true
}
int q = 0; //q tracks if all of the values are false, if all are false then q == n -2
bool changes = true;
for (int m = 0; m < n; ++m) //m is the current point we are working with, changing it
{
for (int j = 0; j <= 50; ++j) //j is the current x value we are trying
for (int k = 0; k <= 50; ++k) //k is the current y value we are trying
{
bool equal = false;
for (int l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (j == x[l] && k == y[l])
equal = true;
}
if (!equal) //if this isn't a point we already have....
{
x2[m] = j; //set this point to j, k
y2[m] = k;

for (int i = 0; i < (n - 2); ++i) // do the same math as above
{
double a = sqrt((x2[i + 1] - x2[i])*(x2[i + 1] - x2[i]) + (y2[i + 1] - y2[i])*(y2[i + 1] - y2[i]));
double b = sqrt((x2[i + 2] - x2[i + 1])*(x2[i + 2] - x2[i + 1]) + (y2[i + 2] - y2[i + 1])*(y2[i + 2] - y2[i + 1]));
double c = sqrt((x2[i + 2] - x2[i])*(x2[i + 2] - x2[i]) + (y2[i + 2] - y2[i])*(y2[i + 2] - y2[i]));

double angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi);

if (angle <= test) // if the angle is now <= 45 set this to false, then repeat to see if all angles are <=45
{
change[i] = false;

}

}

x2 = x; //reset our values
y2 = y;

for (int i = 0; i < (n - 2); ++i) //test to see if all the values are false now
{
if (change[i] == false)
++q;
}
if (q == (n - 2)) //if all the values are false now, break the for loop and give the final answer for this test case
{
changes = false;
goto skip;
}
q = 0;  //reset our q
for (int i = 0; i < n - 2; ++i) //reset the bool array
change[i] = true;
}
}

}

skip:
if (sharp == true && changes == true)   //if there are sharp turns, and changing the points does not remove the sharp turn, no no
cout << "no no" << '\n';
else if (sharp == false)                //If there are no sharp turns, the second is automatically a yes as well, yes yes
cout << "yes yes" << '\n';
else if (sharp == true && changes == false) //if there are sharp turns, and changing the points can remove it, no yes
cout << "no yes";
}

return 0;
}


Code organisation and tests

The problem you are given provides examples. It would be very helpful to take this chance to write automated tests based on these examples (and you could add more) to be able to have some confidence while updating the code. Also, while doing so, you usually split your code into smaller functions easier to understand, make it more documented and separate the concerns (the logic handling input/output is removed out of the logic performing computations).

The obvious input from your code seems to be to define a function taking 2 vectors as arguments and returning the result of the sharp turn analysis. The return value could be a string but it would make sense to define an enum to have a proper name for the different situations and make this independant from how things gets printed later on.

You could write something like:

// https://codereview.stackexchange.com/questions/189441/solving-for-45-degree-angles-of-a-multi-vector-system
#include <iostream>
#include <vector>
#include<cmath>

using namespace std;

enum SharpTurnResult
{
UNKNOWN,
NO_SHARP_TURN,
SHARP_TURN_MODIFIABLE,
SHARP_TURN_NOT_MODIFIABLE,
};

SharpTurnResult analyseSharpTurns(vector<double> x, vector<double> y)
{
int n = x.size();
double pi = 3.1415926535897;
const double test = 45.0000000000;
bool sharp = false;
for (int i = 0; i < (n - 2); ++i)   //calculates the angle of each vertex in the system
{
double a = sqrt((x[i + 1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));
double b = sqrt((x[i + 2] - x[i+1])*(x[i + 2] - x[i+1]) + (y[i + 2] - y[i+1])*(y[i + 2] - y[i+1]));
double c = sqrt((x[i + 2] - x[i])*(x[i + 2] - x[i]) + (y[i + 2] - y[i])*(y[i + 2] - y[i]));

//calculating the length of each side (c is not an actual side, used for the angle calculation)

double angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi); //calculating the angle

if (angle > test) //if the angle is larger than "test" (45), we have a sharp turn, set to true;
{
sharp = true;
}
}

vector<double> x2 = x;
vector<double> y2 = y;     //set the values of x2 and y2 to their original values before manipulation

vector<bool> change; //testing to see if we can change all angles to <45
change.resize(n-2); //need all of the angles to be <= 45, so create an array of bools to see if all angles changes to false

for (int i = 0; i < (n - 2); ++i)
{
change[i] = true;       //set to default true
}
int q = 0; //q tracks if all of the values are false, if all are false then q == n -2
bool changes = true;
for (int m = 0; m < n; ++m) //m is the current point we are working with, changing it
{
for (int j = 0; j <= 50; ++j) //j is the current x value we are trying
for (int k = 0; k <= 50; ++k) //k is the current y value we are trying
{
bool equal = false;
for (int l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (j == x[l] && k == y[l])
equal = true;
}
if (!equal) //if this isn't a point we already have....
{
x2[m] = j; //set this point to j, k
y2[m] = k;

for (int i = 0; i < (n - 2); ++i) // do the same math as above
{
double a = sqrt((x2[i + 1] - x2[i])*(x2[i + 1] - x2[i]) + (y2[i + 1] - y2[i])*(y2[i + 1] - y2[i]));
double b = sqrt((x2[i + 2] - x2[i + 1])*(x2[i + 2] - x2[i + 1]) + (y2[i + 2] - y2[i + 1])*(y2[i + 2] - y2[i + 1]));
double c = sqrt((x2[i + 2] - x2[i])*(x2[i + 2] - x2[i]) + (y2[i + 2] - y2[i])*(y2[i + 2] - y2[i]));

double angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi);

if (angle <= test) // if the angle is now <= 45 set this to false, then repeat to see if all angles are <=45
{
change[i] = false;

}

}

x2 = x; //reset our values
y2 = y;

for (int i = 0; i < (n - 2); ++i) //test to see if all the values are false now
{
if (change[i] == false)
++q;
}
if (q == (n - 2)) //if all the values are false now, break the for loop and give the final answer for this test case
{
changes = false;
goto skip;
}
q = 0;  //reset our q
for (int i = 0; i < n - 2; ++i) //reset the bool array
change[i] = true;
}
}

}

skip:
if (sharp == true && changes == true)   //if there are sharp turns, and changing the points does not remove the sharp turn, no no
return SHARP_TURN_NOT_MODIFIABLE;
else if (sharp == false)                //If there are no sharp turns, the second is automatically a yes as well, yes yes
return NO_SHARP_TURN;
else if (sharp == true && changes == false) //if there are sharp turns, and changing the points can remove it, no yes
return SHARP_TURN_MODIFIABLE;
return UNKNOWN;
}

int main()
{
if (true)
{
double x1[] = {0, 1, 2};
double y1[] = {0, 1, 1};
vector<double> x_vec1(x1, x1 + sizeof(x1)/sizeof(x1));
vector<double> y_vec1(y1, y1 + sizeof(y1)/sizeof(y1));
cout << (analyseSharpTurns(x_vec1, y_vec1) == NO_SHARP_TURN);

double x2[] = {0, 1, 6};
double y2[] = {0, 0, 1};
vector<double> x_vec2(x2, x2 + sizeof(x2)/sizeof(x2));
vector<double> y_vec2(y2, y2 + sizeof(y2)/sizeof(y2));
cout << (analyseSharpTurns(x_vec2, y_vec2) == NO_SHARP_TURN);

double x3[] = {0, 1, 1};
double y3[] = {0, 0, 1};
vector<double> x_vec3(x3, x3 + sizeof(x3)/sizeof(x3));
vector<double> y_vec3(y3, y3 + sizeof(y3)/sizeof(y3));
cout << (analyseSharpTurns(x_vec3, y_vec3) == SHARP_TURN_MODIFIABLE);

double x4[] = {0, 1, 1, 6};
double y4[] = {0, 0, 1, 1};
vector<double> x_vec4(x4, x4 + sizeof(x4)/sizeof(x4));
vector<double> y_vec4(y4, y4 + sizeof(y4)/sizeof(y4));
cout << (analyseSharpTurns(x_vec4, y_vec4) == SHARP_TURN_MODIFIABLE);

double x5[] = {0, 1, 1, 2, 2, 3};
double y5[] = {0, 0, 1, 1, 2, 2};
vector<double> x_vec5(x5, x5 + sizeof(x5)/sizeof(x5));
vector<double> y_vec5(y5, y5 + sizeof(y5)/sizeof(y5));
cout << (analyseSharpTurns(x_vec5, y_vec5) == SHARP_TURN_NOT_MODIFIABLE);
}
else
{
int t;
cin >> t;   //Input the number of test cases
while (t--)
{
int n;

cin >> n;   //Input the number of points for this test case
vector<double> x, y, x2, y2; //x and y are the copies that do not get changes, x2 and y2 are changed and reset back to x/y
x.resize(n);
y.resize(n);

for (int i = 0; i < n; ++i) //Input "n" points
{
cin >> x[i];
cin >> y[i];
}

switch(analyseSharpTurns(x, y))
{
case UNKNOWN:                   cout << "OOOOOPS"; break;
case NO_SHARP_TURN:             cout << "yes yes\n"; break;
case SHARP_TURN_MODIFIABLE:     cout << "no yes\n"; break;
case SHARP_TURN_NOT_MODIFIABLE: cout << "no no\n"; break;
}
}
}
return 0;
}


Realistically, you could use a proper test framework or just assert but this is enough for the time being: we have the base cases tested and we have a small, well-defined function with a clear input and a clear output.

It is now much easier to improve the code.

Boolean conditions

Instead of writing if (cond == true) (or if (cond == false)), you could/should write if (cond) (or if (!cond)).

Also, it would make sense to re-organise the checks and conditions to write/compute a minimal amount of conditions. Also, this makes obvious the fact that we never reach the end of the function.

if (!sharp)
return NO_SHARP_TURN;
return changes ? SHARP_TURN_NOT_MODIFIABLE : SHARP_TURN_MODIFIABLE;


Yet another small function

Most of the trigonometry can be moved into a function on its own:

double computeAngle(double x0, double x1, double x2, double y0, double y1, double y2)
{
double pi = 3.1415926535897;
//calculating the length of each side (c is not an actual side, used for the angle calculation)
double a = sqrt((x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0));
double b = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
double c = sqrt((x2 - x0)*(x2 - x0) + (y2 - y0)*(y2 - y0));
return 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi); //calculating the angle
}


Notice that splitting the code into small function somehow removes the need for some comments. Also, you can appreciate the fact that defining variables in a small scope makes this task much easier.

Early break

When you set sharp to true, you can break, there is no need to go any further in the loop. This also applies to equal = true

Also, if no sharp was found, you could return directly from the function without going through the whole logic. Once again, this is easier now that we've defined our logic in a small function (when everything is in the main, you can't easily "return" a partial result).

Also, you can return SHARP_TURN_MODIFIABLE; instead of having a goto and then you return SHARP_TURN_NOT_MODIFIABLE whenever no possible modification was found.

At this stage, the function looks like:

SharpTurnResult analyseSharpTurns(vector<double> x, vector<double> y)
{
int n = x.size();
const double test = 45.0000000000;
bool sharp = false;
for (int i = 0; i < (n - 2); ++i) //calculates the angle of each vertex in the system
{
double angle = computeAngle(x[i], x[i+1], x[i+2], y[i], y[i+1], y[i+2]);
if (angle > test) //if the angle is larger than the limit, we have a sharp turn
{
sharp = true;
break;
}
}
if (!sharp)
return NO_SHARP_TURN;

vector<double> x2 = x;
vector<double> y2 = y; //set the values of x2 and y2 to their original values before manipulation

vector<bool> change; //testing to see if we can change all angles to <45
change.resize(n-2); //need all of the angles to be <= 45, so create an array of bools to see if all angles changes to false

for (int i = 0; i < (n - 2); ++i)
{
change[i] = true;       //set to default true
}
for (int m = 0; m < n; ++m) //m is the current point we are working with, changing it
for (int j = 0; j <= 50; ++j) //j is the current x value we are trying
for (int k = 0; k <= 50; ++k) //k is the current y value we are trying
{
bool equal = false;
for (int l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (j == x[l] && k == y[l])
{
equal = true;
break;
}
}
if (!equal) //if this isn't a point we already have....
{
int q = 0; //q tracks if all of the values are false, if all are false then q == n -2
x2[m] = j; //set this point to j, k
y2[m] = k;

for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(x2[i], x2[i+1], x2[i+2], y2[i], y2[i+1], y2[i+2]);

if (angle <= test) // if the angle is now <= 45 set this to false, then repeat to see if all angles are <=45
{
change[i] = false;
}
}

x2 = x; //reset our values
y2 = y;

for (int i = 0; i < (n - 2); ++i) //test to see if all the values are false now
{
if (change[i] == false)
++q;
}
if (q == (n - 2)) //if all the values are false now, break the for loop and give the final answer for this test case
{
return SHARP_TURN_MODIFIABLE;
}
for (int i = 0; i < n - 2; ++i) //reset the bool array
change[i] = true;
}
}

return SHARP_TURN_NOT_MODIFIABLE;
}


An easier way to find changes

At the moment, you use many loops, a vector and a flag to detect changes. First, we can move the declaration and the initialisation of change in a smaller scope and get rid of the "resetting" logic.

Then, you can get rid of the initialisation loop by writing:

               vector<bool> change; //testing to see if we can change all angles to <45
change.resize(n-2); //need all of the angles to be <= 45, so create an array of bools to see if all angles changes to false
for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(x2[i], x2[i+1], x2[i+2], y2[i], y2[i+1], y2[i+2]);
change[i] = angle > test;
}


Then, you can get rid of the loop to increment q by having this in the same loop:

                for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(x2[i], x2[i+1], x2[i+2], y2[i], y2[i+1], y2[i+2]);
change[i] = angle > test;
if (change[i] == false)
++q;
}


But then, we do not even need change at all:

                for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(x2[i], x2[i+1], x2[i+2], y2[i], y2[i+1], y2[i+2]);
if (angle <= test)
++q;
}


This loop can be stopped when we do not have the condition angle <= test as q will "miss at least one element".

Now, this can be summarized with a single boolean flag (that could be called modifiable or something like that):

SharpTurnResult analyseSharpTurns(vector<double> x, vector<double> y)
{
int n = x.size();
const double test = 45.0000000000;
bool sharp = false;
for (int i = 0; i < (n - 2); ++i) //calculates the angle of each vertex in the system
{
double angle = computeAngle(x[i], x[i+1], x[i+2], y[i], y[i+1], y[i+2]);
if (angle > test) //if the angle is larger than the limit, we have a sharp turn
{
sharp = true;
break;
}
}
if (!sharp)
return NO_SHARP_TURN;

for (int m = 0; m < n; ++m) //m is the current point we are working with, changing it
for (int j = 0; j <= 50; ++j) //j is the current x value we are trying
for (int k = 0; k <= 50; ++k) //k is the current y value we are trying
{
bool equal = false;
for (int l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (j == x[l] && k == y[l])
{
equal = true;
break;
}
}
if (!equal) //if this isn't a point we already have....
{
bool modifiable = true;
vector<double> x2 = x;
vector<double> y2 = y; //set the values of x2 and y2 to their original values before manipulation
x2[m] = j; //set this point to j, k
y2[m] = k;

for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(x2[i], x2[i+1], x2[i+2], y2[i], y2[i+1], y2[i+2]);
if (angle > test)
{
modifiable = false;
break;
}
}

if (modifiable)
return SHARP_TURN_MODIFIABLE;
}
}

return SHARP_TURN_NOT_MODIFIABLE;
}


Minor optimisations in computeAngle

Some square roots are computed only to be squared afterward. This seems sub-optimal.

double aa = (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0);
double bb = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
double cc = (x2 - x0)*(x2 - x0) + (y2 - y0)*(y2 - y0);
return 180 - ((acos((aa + bb - cc) / (2 * sqrt(aa) * sqrt(bb)))) * 180 / pi);


Also, sub-expressions are computed more than once (even if this is probably optimised out by a decent compiler):

The right data structure

You go through 2 vectors to get points coordinates. It would be clearer to have a single vector of Points. You can use a typedef to make your code easier to understand. Also, you can take this chance to pass data using const references to avoid copying it - see miscco's comment.

Your j, k, m loops are independant and can be re-ordered. This is great because, you can iterate over j and k, build a Point(j, k) and only then iterate over m. Then, it becomes clearer that all the logic around the bool equal = false variable can be done out of the m loop as well.

At this stage, after changing the data type and the loop order, the code looks like:

// https://codereview.stackexchange.com/questions/189441/solving-for-45-degree-angles-of-a-multi-vector-system
#include <iostream>
#include <vector>
#include<cmath>

using namespace std;

enum SharpTurnResult
{
NO_SHARP_TURN,
SHARP_TURN_MODIFIABLE,
SHARP_TURN_NOT_MODIFIABLE,
};

typedef pair<double, double> Point;

double computeAngle(double x0, double x1, double x2, double y0, double y1, double y2)
{
double pi = 3.1415926535897;
//calculating the length of each side (c is not an actual side, used for the angle calculation)
double aa = (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0);
double bb = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
double cc = (x2 - x0)*(x2 - x0) + (y2 - y0)*(y2 - y0);
return 180 - ((acos((aa + bb - cc) / (2 * sqrt(aa) * sqrt(bb)))) * 180 / pi);
}

double computeAngle(const Point & p1, const Point & p2, const Point & p3)
{
return computeAngle(p1.first, p2.first, p3.first, p1.second, p2.second, p3.second);
}

SharpTurnResult analyseSharpTurns(const vector<Point> & points)
{
int n = points.size();
const double test = 45.0000000000;
bool sharp = false;
for (int i = 0; i < (n - 2); ++i) //calculates the angle of each vertex in the system
{
double angle = computeAngle(points[i], points[i+1], points[i+2]);
if (angle > test) //if the angle is larger than the limit, we have a sharp turn
{
sharp = true;
break;
}
}
if (!sharp)
return NO_SHARP_TURN;

for (int j = 0; j <= 50; ++j) //j is the current x value we are trying
for (int k = 0; k <= 50; ++k) //k is the current y value we are trying
{
Point p = make_pair(j, k);
bool equal = false;
for (int l = 0; l < n; ++l) //checking to make sure we aren't using a point that already exists in our system
{
if (points[l] == p)
{
equal = true;
break;
}
}

if (!equal) //if this isn't a point we already have....
{
for (int m = 0; m < n; ++m) //m is the current point we are working with, changing it
{
bool modifiable = true;
vector<Point> points2 = points;
points2[m] = p;
for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(points2[i], points2[i+1], points2[i+2]);
if (angle > test)
{
modifiable = false;
break;
}
}

if (modifiable)
return SHARP_TURN_MODIFIABLE;
}
}
}

return SHARP_TURN_NOT_MODIFIABLE;
}

int main()
{
if (true)
{
Point points1[] = {make_pair(0, 0), make_pair(1, 1), make_pair(2, 1)};
vector<Point> points_vec1(points1, points1 + sizeof(points1)/sizeof(points1));
cout << (analyseSharpTurns(points_vec1) == NO_SHARP_TURN);

Point points2[] = {make_pair(0, 0), make_pair(1, 0), make_pair(6, 1)};
vector<Point> points_vec2(points2, points2 + sizeof(points2)/sizeof(points2));
cout << (analyseSharpTurns(points_vec2) == NO_SHARP_TURN);

Point points3[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1)};
vector<Point> points_vec3(points3, points3 + sizeof(points3)/sizeof(points3));
cout << (analyseSharpTurns(points_vec3) == SHARP_TURN_MODIFIABLE);

Point points4[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1), make_pair(6, 1)};
vector<Point> points_vec4(points4, points4 + sizeof(points4)/sizeof(points4));
cout << (analyseSharpTurns(points_vec4) == SHARP_TURN_MODIFIABLE);

Point points5[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1), make_pair(2, 1), make_pair(2, 2), make_pair(3, 2)};
vector<Point> points_vec5(points5, points5 + sizeof(points5)/sizeof(points5));
cout << (analyseSharpTurns(points_vec5) == SHARP_TURN_NOT_MODIFIABLE);
}
else
{
int t;
cin >> t;   //Input the number of test cases
while (t--)
{
int n;

cin >> n;   //Input the number of points for this test case
vector<Point> points;
points.resize(n);

for (int i = 0; i < n; ++i) //Input "n" points
{
double x, y;
cin >> x;
cin >> y;
points[i] = make_pair(x, y);
}

switch(analyseSharpTurns(points))
{
case NO_SHARP_TURN:             cout << "yes yes\n"; break;
case SHARP_TURN_MODIFIABLE:     cout << "no yes\n"; break;
case SHARP_TURN_NOT_MODIFIABLE: cout << "no no\n"; break;
}
}
}
return 0;
}


More data types

You keep looping over your vector to find if a point is already in it. The appropriate data structure for an efficient membership check is a set.

You can build your set once at the beginning, then perform a lookup in a concise way:

set<Point> points_set(points.begin(), points.end());
...
Point p = make_pair(j, k);
if (points_set.find(p) == points_set.end()) //if this isn't a point we already have....


Removing useless copies

Currently, in the nested loop, we copy an entire vector. This could be expensive when the vector gets big.

It is more efficient (but more work for the developer) to perform the copy once and then making sure you restore it to the original content after using it.

You'd have something like:

   vector<Point> points2 = points; // Copy of the original data - we'll update it but make sure we restore it to avoid performing expensive copies
...
bool modifiable = true;
Point orig = points[m]; // save original value
points2[m] = p;
for (int i = 0; i < (n - 2); ++i)
{
double angle = computeAngle(points2[i], points2[i+1], points2[i+2]);
if (angle > test)
{
modifiable = false;
break;
}
}

if (modifiable)
return SHARP_TURN_MODIFIABLE;
points2[m] = orig; // restore original value


Algorithm optimisation

There are major changes possible to the algorithm. Before considering smart optimisations, you should make sure you use proper benchmark tests with big inputs.

Optimisations could include things like:

• try to change coordinates only for the points around the first sharp turn found.

• perform mathematical analysis to know where the point could lay on the plan (not all points are relevant to create a non-sharp turn).

You could have something like:

// Fixing a sharp angle i is done by moving point i-1, i or i+1.
// This could also fix a sharp angle for angles i-2, i-1, i, i+1, i+2.
// If a sharp angle is further, it can't be fixed with a single point moved
int first_sharp = -1;
for (int i = 1; i < n - 1; i++)
{
double angle = computeAngle(points[i-1], points[i], points[i+1]);
if (angle > test) //if the angle is larger than the limit, we have a sharp turn
{
if (first_sharp < 0) // first
{
first_sharp = i;
}
else if (i - first_sharp > 2) // too far from first
{
return SHARP_TURN_NOT_MODIFIABLE;
}
}
}
if (first_sharp < 0)
return NO_SHARP_TURN;


Also, we could use this value when trying to move a point:

           for (int m = first_sharp - 1; m < first_sharp + 2; ++m) //m is the index we are moving (around first_sharp)
{
assert (m >= 0 && m < n);
...


Finally, you could also change the i loop to only consider the angles around the point changed.

                int min_i = max(m-1, 1);
int max_i = min(m+2, n-1);
for (int i = min_i; i < max_i; i++)
{
assert (i-1 >= 0 && i+1 < n);
double angle = computeAngle(points2[i-1], points2[i], points2[i+1]);


As mentionned, this can still be improved but at this stage, the code looks like:

// https://codereview.stackexchange.com/questions/189441/solving-for-45-degree-angles-of-a-multi-vector-system
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <assert.h>

using namespace std;

enum SharpTurnResult
{
NO_SHARP_TURN,
SHARP_TURN_MODIFIABLE,
SHARP_TURN_NOT_MODIFIABLE,
};

typedef pair<double, double> Point;

double computeAngle(double x0, double x1, double x2, double y0, double y1, double y2)
{
double pi = 3.1415926535897;
//calculating the length of each side (c is not an actual side, used for the angle calculation)
double aa = (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0);
double bb = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
double cc = (x2 - x0)*(x2 - x0) + (y2 - y0)*(y2 - y0);
return 180 - ((acos((aa + bb - cc) / (2 * sqrt(aa) * sqrt(bb)))) * 180 / pi);
}

double computeAngle(const Point & p1, const Point & p2, const Point & p3)
{
return computeAngle(p1.first, p2.first, p3.first, p1.second, p2.second, p3.second);
}

SharpTurnResult analyseSharpTurns(const vector<Point> & points)
{
int n = points.size();
const double test = 45.0000000000;
// Fixing a sharp angle i is done by moving point i-1, i or i+1.
// This could also fix a sharp angle for angles i-2, i-1, i, i+1, i+2.
// If a sharp angle is further, it can't be fixed with a single point moved
int first_sharp = -1;
for (int i = 1; i < n - 1; i++)
{
double angle = computeAngle(points[i-1], points[i], points[i+1]);
if (angle > test) //if the angle is larger than the limit, we have a sharp turn
{
if (first_sharp < 0) // first
{
first_sharp = i;
}
else if (i - first_sharp > 2) // too far from first
{
return SHARP_TURN_NOT_MODIFIABLE;
}
}
}
if (first_sharp < 0)
return NO_SHARP_TURN;

set<Point> points_set(points.begin(), points.end());
vector<Point> points2 = points; // Copy of the original data - we'll update it but make sure we restore it to avoid performing expensive copies

for (int j = 0; j <= 50; ++j)
for (int k = 0; k <= 50; ++k)
{
Point p = make_pair(j, k);
if (points_set.find(p) == points_set.end()) //if this isn't a point we already have....
{
for (int m = first_sharp - 1; m < first_sharp + 2; ++m) //m is the index we are moving (around first_sharp)
{
assert (m >= 0 && m < n);
bool modifiable = true;
Point orig = points[m]; // save original value
points2[m] = p;
int min_i = max(m-1, 1);
int max_i = min(m+2, n-1);
for (int i = min_i; i < max_i; i++)
{
assert (i-1 >= 0 && i+1 < n);
double angle = computeAngle(points2[i-1], points2[i], points2[i+1]);
if (angle > test)
{
modifiable = false;
break;
}
}

if (modifiable)
return SHARP_TURN_MODIFIABLE;
points2[m] = orig; // restore original value
}
}
}

return SHARP_TURN_NOT_MODIFIABLE;
}

int main()
{
if (true)
{
Point points1[] = {make_pair(0, 0), make_pair(1, 1), make_pair(2, 1)};
vector<Point> points_vec1(points1, points1 + sizeof(points1)/sizeof(points1));
cout << (analyseSharpTurns(points_vec1) == NO_SHARP_TURN);

Point points2[] = {make_pair(0, 0), make_pair(1, 0), make_pair(6, 1)};
vector<Point> points_vec2(points2, points2 + sizeof(points2)/sizeof(points2));
cout << (analyseSharpTurns(points_vec2) == NO_SHARP_TURN);

Point points3[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1)};
vector<Point> points_vec3(points3, points3 + sizeof(points3)/sizeof(points3));
cout << (analyseSharpTurns(points_vec3) == SHARP_TURN_MODIFIABLE);

Point points4[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1), make_pair(6, 1)};
vector<Point> points_vec4(points4, points4 + sizeof(points4)/sizeof(points4));
cout << (analyseSharpTurns(points_vec4) == SHARP_TURN_MODIFIABLE);

Point points5[] = {make_pair(0, 0), make_pair(1, 0), make_pair(1, 1), make_pair(2, 1), make_pair(2, 2), make_pair(3, 2)};
vector<Point> points_vec5(points5, points5 + sizeof(points5)/sizeof(points5));
cout << (analyseSharpTurns(points_vec5) == SHARP_TURN_NOT_MODIFIABLE);
}
else
{
int t;
cin >> t;   //Input the number of test cases
while (t--)
{
int n;

cin >> n;   //Input the number of points for this test case
vector<Point> points;
points.resize(n);

for (int i = 0; i < n; ++i) //Input "n" points
{
double x, y;
cin >> x;
cin >> y;
points[i] = make_pair(x, y);
}

switch(analyseSharpTurns(points))
{
case NO_SHARP_TURN:             cout << "yes yes\n"; break;
case SHARP_TURN_MODIFIABLE:     cout << "no yes\n"; break;
case SHARP_TURN_NOT_MODIFIABLE: cout << "no no\n"; break;
}
}
}
return 0;
}

• You pass the vectors bycopywhich is quite expensive especially in code challenges – miscco Mar 13 '18 at 8:00
• Indeed, const references would probably be more than enough here... Good point! – SylvainD Mar 13 '18 at 8:46
• Minor precision issue: I am curious why use double pi = 3.1415926535897; when double is usually good to at least 15 digits and this is not even rounded right for 14 digits.. I'd expect double pi = 3.1415926535897932384626433832795 and let the compiler use what it can. Maybe even perform a one-time double pi = acos(-1); Or is that just to be in agreement with OP's code? – chux - Reinstate Monica Mar 13 '18 at 12:25
• @chux I haven't changed that part. Feel free to add an answer if you have something to comment about this. – SylvainD Mar 13 '18 at 13:29
• Thank you for the detailed response, I am still working out the details but your explanation was very helpful! – Denis Mar 16 '18 at 13:55

## Inefficient calculation

A compiler may see the redundant subtraction ((x[i + 1] - x[i])*(x[i + 1] - x[i]), but optimizing out the square of a square root is not something I'd expect a compiler to do and so could be improved changing code.

// was
a = sqrt((x[i+1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));
b = sqrt((x[i+2] - x[i+1])*(x[i + 2] - x[i+1]) + (y[i + 2] - y[i+1])*(y[i + 2] - y[i+1]));
c = sqrt((x[i+2] - x[i])*(x[i + 2] - x[i]) + (y[i + 2] - y[i])*(y[i + 2] - y[i]));

angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi);
if (angle > test) {
sharp = true;
}


// suggest
double test_radian = pi(1.0 - test/180.0);  // do this outside loop

// loop code
double dx = x[i + 1] - x[i];
double dy = y[i + 1] - y[i];
double aa = dx*dx + dy*dy;
dx = x[i + 2] - x[i + 1];
dy = y[i + 2] - y[i + 1];
double bb = dx*dx + dy*dy;
dx = x[i + 2] - x[i];
dy = y[i + 2] - y[i];
double cc = dx*dx + dy*dy;

double angle_radian = acos(aa + bb - cc)/(2*sqrt(aa)*sqrt(bb));
sharp = true;
}


Code could take advantage the the previous iteration bb is now the next aa and save that computation too.

Advanced idea: this whole approach can be simplified using mostly integer math.

I have not yet coded a solution yet it go like this.

Consider each set of 3 points: (x0,y0), (x1,y1), (x2,y2). Form points D and E which are extensions of segment P0,P1 and then +/- 45 degrees off for a distance of P1,P2. If P0,P2 is less than P0,D and P0,E, then it is a sharp angle.

Ditch "stdafx.h". It's not a standard header, and the code compiles fine without it.

Get rid of using namespace std;.

Importing all names of a namespace is a bad habit to get into, and can cause surprise when names like begin and size are in the global namespace. Get used to using the namespace prefix (std is intentionally very short), or importing just the names you need into the smallest reasonable scope.

The exceptions to this rule are namespaces explicitly intended to be imported wholesale, such as the std::literals namespaces.

# Reduce scope of variables and improve their names

This looks like the work of a Fortran (or early C) programmer:

int t, n, i, j, k, l, m, iteration = 0, z, q=0;
double a, b, c, angle, pi = 3.1415926535897, test = 45.0000000000;
bool sharp = false, equal = false, changes = true;


What are these all for? Why isn't pi a constant? A less error-prone way of writing π is 4*std::atan(1) (that's a constant expression, so evaluated at compilation time).

# Avoid parallel containers

Instead of creating separate vectors of x and y coordinates, it's better to declare a "point" structure and have a single vector of points. This gives better locality of reference, and also avoids a class of error caused by failure to keep the two in sync.

Consider this statement:

            a = std::sqrt((x[i + 1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));


That looks like a long-winded and obfuscated way of writing

            a = std::hypot(x[i+1] - x[i],  y[i+1] - y[i]);


# Don't complete loops unnecessarily

The same loop has

            if (angle > test) {
sharp = true;
}


Since setting sharp is the only side-effect of this loop, there's no need to do any more work here:

            if (angle > test) {
sharp = true;
break;
}


It seems that you're more comfortable in degrees than radians, so tend to convert values to degrees. It's going to be more effective to convert your constraint to radians and then work consistent in radians (which are more natural to <cmath> trigonometry).

No need to write a loop for this:

    for (i = 0; i < (n - 2); ++i) {
change[i] = true;       //set to default true
}


It's clearer and less error prone to

   std::fill(change.begin(), change.end(), true);


But in any case, beware that you're working with std::vector<bool> here, which is optimised for compact storage at the expense of speed (and compatibility). You might be better off with a vector of char.

# Long-winded redundant comparisons

The bool variables are already boolean and can be tested directly. And these comments don't add any insight:

    if (sharp == true && changes == true)   //if there are sharp turns, and changing the points does not remove the sharp turn, no no
cout << "no no" << '\n';
else if (sharp == false)                //If there are no sharp turns, the second is automatically a yes as well, yes yes
cout << "yes yes" << '\n';
else if (sharp == true && changes == false) //if there are sharp turns, and changing the points can remove it, no yes
cout << "no yes";


And we can reduce the number of tests in the chain by re-ordering the conditions:

    if (!sharp) {
// no sharp turns
cout << "yes yes\n";
} else if (changes) {
// sharp turns can be removed
cout << "no yes";
} else {
// sharp turns cannot be removed
cout << "no no\n";
}

    for (i = 0; i < (n - 2); ++i)   //calculates the angle of each vertex in the system
{
a = sqrt((x[i + 1] - x[i])*(x[i + 1] - x[i]) + (y[i + 1] - y[i])*(y[i + 1] - y[i]));
b = sqrt((x[i + 2] - x[i+1])*(x[i + 2] - x[i+1]) + (y[i + 2] - y[i+1])*(y[i + 2] - y[i+1]));
c = sqrt((x[i + 2] - x[i])*(x[i + 2] - x[i]) + (y[i + 2] - y[i])*(y[i + 2] - y[i]));

//calculating the length of each side (c is not an actual side, used for the angle calculation)

angle = 180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi); //calculating the angle

if (angle > test) //if the angle is larger than "test" (45), we have a sharp turn, set to true;
{
sharp = true;
}
}


Why calculate angle?

180 - ((acos((a*a + b*b - c*c) / (2 * a * b))) * 180 / pi) > test


which is equivalent to

acos((a*a + b*b - c*c) / (2 * a * b)) < 3/4 * pi


which is equivalent to

(a*a + b*b - c*c) / (2 * a * b) > -1 / sqrt(2)


which is equivalent to

a*a + b*b + sqrt(2) * a * b > c*c


Since a and b are both known to be positive that can be pushed further as

a*a + b*b + sqrt(2 * a*a * b*b) > c*c


meaning that you save two sqrts and one acos.

Alternatively, working forwards, if the points are PQR (P = (x[i], y[i]), etc.) then the sharpness condition is that $$\widehat{Q-P} \cdot \widehat{R-Q} < \frac{1}{\sqrt 2}$$ which is equivalent to $$(Q-P) \cdot (R-Q) < \frac{\sqrt{(Q-P)\cdot(Q-P)} \sqrt{(R-Q) \cdot (R-Q)}}{\sqrt 2}$$

corresponding to

    for (i = 0; i < (n - 2); ++i)
{
double dx1 = x[i + 1] - x[i];
double dx2 = x[i + 2] - x[i + 1];
double dy1 = y[i + 1] - y[i];
double dy2 = y[i + 2] - y[i + 1];

double lhs = dx1 * dx2 + dy1 * dy2;
double rhs = std::sqrt((dx1 * dx1 + dy1 * dy1) * (dx2 * dx2 + dy2 * dy2) / 2);

if (lhs < rhs)
{
sharp = true;
break;
}
}


The sqrt could even be eliminated as

        double lhs = dx1 * dx2 + dy1 * dy2;
double rhs2 = (dx1 * dx1 + dy1 * dy1) * (dx2 * dx2 + dy2 * dy2) / 2;

if (lhs < 0 || lhs * lhs < rhs2)
{
sharp = true;
break;
}


And because this iteration's dx2, dy2 are next iteration's dx1, dy1 there is the potential to create some variables with wider scope and reuse the value of the subexpression which depends solely on those values.