Sponsored
Sponsored
In this approach, we calculate the slope between the first two points and then compare this slope with that of subsequent points. The slope between two points (x1, y1) and (x2, y2) is given by (y2-y1)/(x2-x1). For all points to lie on the same line, this slope should be constant for every pair of consecutive points.
Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a fixed number of extra variables.
1#include <stdbool.h>
2
3bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize) {
4 int x1 = coordinates[0][0], y1 = coordinates[0][1];
5 int x2 = coordinates[1][0], y2 = coordinates[1][1];
6 for (int i = 2; i < coordinatesSize; i++) {
7 int x = coordinates[i][0], y = coordinates[i][1];
8 if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
9 return false;
10 }
11 }
12 return true;
13}This C solution checks the constancy of slope using cross multiplication to avoid division and potential floating point precision issues. It iterates through all points starting from the third point and compares the calculated product terms for collinearity.
This approach uses the cross-product method which is useful for determining collinearity without explicitly calculating slopes. For every pair of consecutive vectors, compute the cross product to determine if they are collinear. If all cross products are zero, the points are collinear.
Time Complexity: O(n), where n refers to the number of coordinates.
Space Complexity: O(1), as only constant additional space is used.
1using namespace std;
bool checkStraightLine(vector<vector<int>>& coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (size_t i = 2; i < coordinates.size(); ++i) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) return false;
}
return true;
}The C++ code calculates cross products for vectors represented by consecutive points. Equal cross-products ensure collinearity, achieved without slope division.