MiddleCodeOccasionalNot answered yet
Check whether all integer points are collinear
Given a list of points with integer coordinates, return true if they all lie on a single straight line.
Requirements:
- Avoid floating-point slope
(y2-y1)/(x2-x1)— it loses precision and divides by zero on vertical lines. - Watch for integer overflow in the cross product.
struct Point { int x, y; };
bool areCollinear(const std::vector<Point>& pts) {
// your code here
}Write the implementation.
Fix the first two points as a reference direction (dx, dy). A point p is on that line iff the cross product dx*(p.y-y0) - dy*(p.x-x0) is zero. Check it for every point. Use long long for the products to avoid overflow; no division means vertical lines work too. O(n).
- ✗Using floating-point slope, losing precision or dividing by zero on a vertical line
- ✗Computing the cross product in
int, overflowing on large coordinates - ✗Testing only a subset of points instead of every point against the reference line
- →Why is the cross product preferred over comparing slopes?
- →What edge cases arise with fewer than three points?
Contents
Task
Check whether all integer points are collinear, without floating-point slope.
Solution
bool areCollinear(const std::vector<Point>& pts) {
if (pts.size() < 3) return true;
long long x0 = pts[0].x, y0 = pts[0].y;
long long dx = pts[1].x - x0, dy = pts[1].y - y0;
for (const auto& p : pts) {
long long cross = dx * (p.y - y0) - dy * (p.x - x0);
if (cross != 0) return false;
}
return true;
}Key points
- A cross product
== 0replaces slope comparison — no division, no float. long longguards against overflow on large coordinates.- Vertical lines are handled naturally since there is no division.
Contents
