Векторлар

Вектор деген не?

Вектор — бағыты және ұзындығы бар объект.

Жазықтықта vector көбіне екі coordinate арқылы беріледі:

v = (x, y)

Мысалы:

v = (3, 4)

Бұл vector 3 бірлік оңға және 4 бірлік жоғары қарай жүреді деген сөз.

Екі нүкте арасындағы vector

Екі нүкте берілсін:

A = (x1, y1)
B = (x2, y2)

Онда A-дан B-ға vector:

AB = (x2 - x1, y2 - y1)

Мысал:

A = (2, 1)
B = (7, 4)

AB = (7 - 2, 4 - 1) = (5, 3)

Point struct

Geometry задачаларында point пен vector-ды бірдей struct арқылы сақтау ыңғайлы.

struct Point {
    long long x;
    long long y;
};

Егер Point point координатасын сақтаса, екі point-тың айырмасы vector береді.

Vector операциялары

Операторлар қосуға болады:

struct Point {
    long long x;
    long long y;

    Point operator + (const Point &other) const {
        return {x + other.x, y + other.y};
    }

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }

    Point operator * (long long k) const {
        return {x * k, y * k};
    }
};

Енді былай жазуға болады:

Point c = a + b;
Point v = b - a;
Point t = v * 3;

Vector қосу

Егер:

a = (x1, y1)
b = (x2, y2)

Онда:

a + b = (x1 + x2, y1 + y2)

Мысал:

(2, 3) + (5, 1) = (7, 4)

Vector азайту

Егер:

a = (x1, y1)
b = (x2, y2)

Онда:

a - b = (x1 - x2, y1 - y2)

Мысал:

(7, 4) - (2, 3) = (5, 1)

Vector-ды санға көбейту

Vector-ды санға көбейтсек, оның координаталары да сол санға көбейеді.

k * (x, y) = (k * x, k * y)

Мысал:

3 * (2, 5) = (6, 15)

Егер k оң болса, direction сақталады. Егер k теріс болса, direction қарама-қарсы өзгереді.

Vector ұзындығы

v = (x, y) vector-ының length:

|v| = sqrt(x^2 + y^2)

Мысал:

v = (3, 4)

|v| = sqrt(3^2 + 4^2) = 5

Length коды

double length(Point v) {
    return sqrt(v.x * v.x + v.y * v.y);
}

Егер тек length салыстыру керек болса, квадрат length қолданған жақсы.

Квадрат length

Квадрат length:

|v|^2 = x^2 + y^2

Код:

long long length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

Бұл ыңғайлы, себебі:

sqrt жоқ
double error жоқ
тез жұмыс істейді

Екі point арасындағы distance

A және B point-тары арасындағы distance — бұл B - A vector-ының length-і.

double dist(Point a, Point b) {
    return length(b - a);
}

Квадрат distance:

long long dist2(Point a, Point b) {
    return length2(b - a);
}

Скалярлық көбейтінді

Скалярлық көбейтінді, немесе dot product:

dot(a, b) = a.x * b.x + a.y * b.y

Код:

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

dot нені көрсетеді?

Dot екі vector арасындағы angle-ды түсінуге көмектеседі.

dot(a, b) > 0 → angle сүйір
dot(a, b) = 0 → angle 90°
dot(a, b) < 0 → angle доғал

Сондықтан dot көбіне perpendicular тексеру үшін қолданылады.

Перпендикулярлық

Екі vector perpendicular болады, егер:

dot(a, b) = 0

Код:

bool perpendicular(Point a, Point b) {
    return dot(a, b) == 0;
}

Мысал:

a = (1, 0)
b = (0, 1)

dot(a, b) = 0

Vector арасындағы angle

Екі vector арасындағы angle dot арқылы табылады:

cos(angle) = dot(a, b) / (|a| * |b|)

Код:

double angle(Point a, Point b) {
    double value = dot(a, b) / (length(a) * length(b));

    value = max(-1.0, min(1.0, value));

    return acos(value);
}

max/min double error үшін керек: value 1-ден сәл асып кетуі немесе -1-ден сәл кіші болуы мүмкін.

Векторлық көбейтінді

2D geometry ішінде векторлық көбейтінді, немесе cross product:

cross(a, b) = a.x * b.y - a.y * b.x

Код:

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

cross нені көрсетеді?

Cross бірінші vector-дан екінші vector-ға бұрылғанда direction көрсетеді.

cross(a, b) > 0 → b, a-ның сол жағында
cross(a, b) < 0 → b, a-ның оң жағында
cross(a, b) = 0 → vector-лар бір түзудің бойында

Бұл turn, orientation және segment intersection задачалары үшін ең маңызды операция.

Коллинеар vector-лар

Екі vector collinear болады, егер олар бір түзудің бойында жатса.

Шарт:

cross(a, b) = 0

Код:

bool collinear(Point a, Point b) {
    return cross(a, b) == 0;
}

Үш point orientation-ы

A, B, C үш point үшін C point-ы бағытталған AB segment-іне қатысты қай жерде тұрғанын табуға болады.

Есептейміз:

cross(B - A, C - A)

> 0 → C AB-ның сол жағында
< 0 → C AB-ның оң жағында
= 0 → A, B, C бір түзуде

Orientation коды

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

Қолдану мысалы:

long long val = orient(a, b, c);

if (val > 0) {
    cout << "LEFT";
} else if (val < 0) {
    cout << "RIGHT";
} else {
    cout << "COLLINEAR";
}

Area cross арқылы

Cross модулі екі vector құрған parallelogram area-сына тең.

area_parallelogram = abs(cross(a, b))

Triangle area одан 2 есе кіші:

area_triangle = abs(cross(a, b)) / 2

ABC triangle area

A, B, C point-тары үшін:

area2 = abs(cross(B - A, C - A))

Бұл екі еселенген area.

Код:

long long triangleArea2(Point a, Point b, Point c) {
    return abs(cross(b - a, c - a));
}

Vector-ды 90 градусқа бұру

Егер vector:

v = (x, y)

Онда 90 градусқа сағат тіліне қарсы бұру:

(-y, x)

90 градусқа сағат тілімен бұру:

(y, -x)

Код: 90 градусқа бұру

Point rotate90Left(Point v) {
    return {-v.y, v.x};
}

Point rotate90Right(Point v) {
    return {v.y, -v.x};
}

Бұл perpendicular vector алу үшін жиі қолданылады.

Кез келген angle-ға бұру

Vector-ды angle бұрышына бұру керек болса, sin және cos қолданамыз.

newX = x * cos(angle) - y * sin(angle)
newY = x * sin(angle) + y * cos(angle)

Код:

struct DPoint {
    double x;
    double y;
};

DPoint rotate(DPoint p, double angle) {
    double cs = cos(angle);
    double sn = sin(angle);

    return {
        p.x * cs - p.y * sn,
        p.x * sn + p.y * cs
    };
}

C++ ішінде sin, cos, acos үшін angle радианмен беріледі.

Vector projection

a vector-ының b vector-ына projection-ы — a-ның қанша бөлігі b direction бойынша жатқанын көрсетеді.

Projection length:

dot(a, b) / |b|

Егер нақты формула керек болса, көбіне double қолданамыз.

Polar angle бойынша sort

Кейде point-тарды немесе vector-ларды origin-ге қатысты angle бойынша sort жасау керек.

Оңай әдіс — atan2 қолдану:

double getAngle(Point p) {
    return atan2(p.y, p.x);
}

Sort:

sort(a.begin(), a.end(), [](Point p1, Point p2) {
    return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
});

atan2 angle-ды радианмен -pi мен pi арасында қайтарады.

Vector нормализациясы

Кейде vector-ды unit length-ке келтіру керек. Бұл нормализация деп аталады.

unit = v / |v|

Бұл үшін double керек:

DPoint normalize(DPoint v) {
    double len = sqrt(v.x * v.x + v.y * v.y);

    return {v.x / len, v.y / len};
}

Zero vector нормализация жасауға болмайды, себебі оның length-і 0.

Zero vector

Zero vector:

(0, 0)

Оның length-і 0. Оның direction-ы жоқ.

Тексеру:

bool isZero(Point v) {
    return v.x == 0 && v.y == 0;
}

Толық базалық template

#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x;
    long long y;

    Point operator + (const Point &other) const {
        return {x + other.x, y + other.y};
    }

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }

    Point operator * (long long k) const {
        return {x * k, y * k};
    }
};

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

long long length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

double length(Point v) {
    return sqrt(length2(v));
}

long long dist2(Point a, Point b) {
    return length2(b - a);
}

double dist(Point a, Point b) {
    return length(b - a);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Point a, b;
    cin >> a.x >> a.y;
    cin >> b.x >> b.y;

    Point v = b - a;

    cout << v.x << ' ' << v.y << '\n';
    cout << length(v) << '\n';

    return 0;
}

Мысал

Input

2 1
7 4

Output

5 3
5.83095

Мұнда:

A = (2, 1)
B = (7, 4)

AB = (5, 3)

dot қашан қолданылады?

perpendicular тексеру керек → dot == 0
angle сүйір ме, доғал ма білу керек → dot sign
angle табу керек → acos через dot
projection керек → dot
direction салыстыру керек → dot

cross қашан қолданылады?

turn тексеру керек → cross
collinear тексеру керек → cross == 0
area табу керек → abs(cross)
segment intersection тексеру керек → orient арқылы cross
convex hull құру керек → cross

long long немесе double?

Тип	Қашан қолданамыз?
long long	coordinates integer, нақты dot/cross/orient керек
double	length, angle, sin, cos, sqrt керек

Егер coordinates integer болса, dot, cross және orient-ты long long арқылы санаған жақсы.

double үшін EPS

Double сандарды == арқылы салыстыру қауіпті. Кішкентай error болуы мүмкін.

const double EPS = 1e-9;

int cmp(double x) {
    if (x > EPS) {
        return 1;
    }

    if (x < -EPS) {
        return -1;
    }

    return 0;
}

Егер cmp(x) == 0 болса, x нөлге тең деп есептейміз.

Типтік задачалар

vector length табу
екі point арасындағы distance табу
perpendicular тексеру
collinear тексеру
солға немесе оңға turn анықтау
triangle area табу
point-тарды angle бойынша sort жасау
segment intersection тексеру

Типтік қателер

point пен vector-ды шатастыру
AB vector үшін B - A орнына A - B жазу
dot пен cross шатастыру
cross әрқашан positive деп ойлау
coordinates үлкен кезде int қолдану
length2 арқылы салыстыруға болатын жерде sqrt алу
double-ды == арқылы салыстыру
zero vector нормализация жасау

Асимптотика

Операция	Уақыт
Vector қосу	O(1)
Vector азайту	O(1)
Vector length	O(1)
dot	O(1)
cross	O(1)
orientation	O(1)
Angle бойынша sort	O(n log n)

Қысқа template

struct Point {
    long long x;
    long long y;

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }
};

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

long long length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

Ең бастысы

vector = direction + length
AB = B - A
length = sqrt(x² + y²)
dot angle көрсетеді
cross turn көрсетеді
cross == 0 → collinear
dot == 0 → perpendicular