MiddleКодИногдаЕщё не отвечали
Проверить, лежат ли все целочисленные точки на одной прямой
Дан список точек с целочисленными координатами. Верните true, если все они лежат на одной прямой.
Требования:
- Избегайте дробного наклона
(y2-y1)/(x2-x1)— он теряет точность и делит на ноль на вертикали. - Следите за переполнением целых в кросс-произведении.
struct Point { int x, y; };
bool areCollinear(const std::vector<Point>& pts) {
// ваш код здесь
}Допишите реализацию.
Зафиксируйте первые две точки как опорное направление (dx, dy). Точка p на прямой тогда и только тогда, когда кросс-произведение dx*(p.y-y0) - dy*(p.x-x0) равно нулю. Проверьте для каждой точки. Берите long long против переполнения; без деления вертикали тоже работают. O(n).
- ✗Использовать дробный наклон, теряя точность или деля на ноль на вертикали
- ✗Считать кросс-произведение в
int, переполняясь на больших координатах - ✗Проверять лишь часть точек вместо каждой против опорной прямой
- →Почему кросс-произведение предпочтительнее сравнения наклонов?
- →Какие краевые случаи возникают при менее чем трёх точках?
Оглавление
Задача
Проверьте, лежат ли все целочисленные точки на одной прямой, без дробного наклона.
Решение
#include <vector>
struct Point { int x, y; };
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;
}Ключевые моменты
- Кросс-произведение
== 0заменяет сравнение наклонов — без деления и без float. long longзащищает от переполнения на больших координатах.- Вертикали обрабатываются естественно, ведь деления нет.
Оглавление
