Нүкте деген не?

Нүкте жазықтықта екі coordinate арқылы беріледі:

(x, y)

Мысалы:

A = (2, 3)
B = (5, 7)

C++ тілінде нүктені struct арқылы сақтау ыңғайлы:

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

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

Вектор — бағыт пен ұзындықты көрсететін displacement.

Егер A және B нүктелері болса, A-дан B-ға вектор:

AB = (B.x - A.x, B.y - A.y)

Мысалы:

A = (2, 3)
B = (5, 7)

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

Point struct және операциялар

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 v = b - a;

Бұл a нүктесінен b нүктесіне вектор болады.

Екі нүкте арақашықтығы

A(x1, y1) және B(x2, y2) нүктелері арасындағы distance:

dist = sqrt((x2 - x1)^2 + (y2 - y1)^2)

Мысалы:

A = (0, 0)
B = (3, 4)

dist = sqrt(3^2 + 4^2) = 5

Distance коды

double dist(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return sqrt(dx * dx + dy * dy);
}

Квадрат distance

Көп задачада distance-терді салыстыру жеткілікті. Онда квадрат distance қолданамыз.

long long dist2(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return dx * dx + dy * dy;
}

Бұл жақсы, себебі:

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

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

Екі вектордың dot product:

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

C++:

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

dot не үшін керек?

Dot product екі вектор арасындағы бұрышты түсінуге көмектеседі.

Сонымен қатар dot projection және perpendicular тексеру үшін қолданылады.

Перпендикуляр тексеру

Егер екі вектор perpendicular болса, олардың dot product мәні 0 болады.

if (dot(a, b) == 0) {
    cout << "perpendicular";
}

Мысалы:

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

dot = 1 * 0 + 0 * 1 = 0

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

2D geometry ішінде cross product былай есептеледі:

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

C++:

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

cross не үшін керек?

cross бір вектор екіншісіне қатысты қай жаққа бұрылатынын көрсетеді.

Бұл geometry ішіндегі ең маңызды операциялардың бірі.

Үш нүктенің orientation-ы

A, B, C үш нүктесі үшін C нүктесі бағытталған AB segment-інің сол жағында ма, оң жағында ма екенін білу керек.

Есептейміз:

cross(B - A, C - A)

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";
}

Үшбұрыш ауданы

ABC үшбұрышының екі еселенген ауданы:

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

Ал кәдімгі area:

abs(cross(B - A, C - A)) / 2

C++:

double triangle_area(Point a, Point b, Point c) {
    return abs(cross(b - a, c - a)) / 2.0;
}

Нүкте segment үстінде жатыр ма?

P нүктесі AB segment-інің үстінде жатыр ма, соны тексерейік.

Екі шарт керек:

Бірінші шарт:

orient(A, B, P) = 0

Код: нүкте segment үстінде

bool onSegment(Point a, Point b, Point p) {
    if (orient(a, b, p) != 0) {
        return false;
    }

    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

Екі segment intersection

Екі segment берілген:

AB
CD

Олар қиылыса ма, соны анықтау керек.

Негізгі идея: C және D нүктелері AB-ның екі жағында, ал A және B нүктелері CD-ның екі жағында жатуы керек.

Intersection жалпы жағдай

Orientation мәндерін санаймыз:

orient(a, b, c)
orient(a, b, d)
orient(c, d, a)
orient(c, d, b)

Егер sign-дары әртүрлі болса, segment-тер қиылысады.

Код: segment intersection

int sign(long long x) {
    if (x > 0) {
        return 1;
    }

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

    return 0;
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    long long o1 = orient(a, b, c);
    long long o2 = orient(a, b, d);
    long long o3 = orient(c, d, a);
    long long o4 = orient(c, d, b);

    if (sign(o1) * sign(o2) < 0 && sign(o3) * sign(o4) < 0) {
        return true;
    }

    if (onSegment(a, b, c)) {
        return true;
    }

    if (onSegment(a, b, d)) {
        return true;
    }

    if (onSegment(c, d, a)) {
        return true;
    }

    if (onSegment(c, d, b)) {
        return true;
    }

    return false;
}

Segment intersection толық реализация

#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};
    }
};

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);
}

int sign(long long x) {
    if (x > 0) {
        return 1;
    }

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

    return 0;
}

bool onSegment(Point a, Point b, Point p) {
    if (orient(a, b, p) != 0) {
        return false;
    }

    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    long long o1 = orient(a, b, c);
    long long o2 = orient(a, b, d);
    long long o3 = orient(c, d, a);
    long long o4 = orient(c, d, b);

    if (sign(o1) * sign(o2) < 0 && sign(o3) * sign(o4) < 0) {
        return true;
    }

    if (onSegment(a, b, c)) {
        return true;
    }

    if (onSegment(a, b, d)) {
        return true;
    }

    if (onSegment(c, d, a)) {
        return true;
    }

    if (onSegment(c, d, b)) {
        return true;
    }

    return false;
}

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

    Point a, b, c, d;

    cin >> a.x >> a.y;
    cin >> b.x >> b.y;
    cin >> c.x >> c.y;
    cin >> d.x >> d.y;

    if (segmentsIntersect(a, b, c, d)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Көпбұрыш ауданы

Егер polygon vertex-тері ретімен берілсе, area-ны cross қосындысы арқылы табуға болады.

Формула:

area2 = abs(sum(cross(p[i], p[i + 1])))

Бұл екі еселенген area. Кәдімгі area:

area = area2 / 2

Код: polygon area

long long polygon_area2(vector<Point> p) {
    int n = p.size();

    long long s = 0;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        s += cross(a, b);
    }

    return abs(s);
}

Кәдімгі area шығару:

long long area2 = polygon_area2(p);

if (area2 % 2 == 0) {
    cout << area2 / 2;
} else {
    cout << area2 / 2 << ".5";
}

Area мысалы

Квадрат:

(0,0)
(2,0)
(2,2)
(0,2)

Оның area:

4

Екі еселенген area:

8

Дөңес көпбұрыш

Дөңес көпбұрыш — барлық бұрылыс бір бағытта болатын polygon.

Тексеру:

Код: convex тексеру

bool isConvex(vector<Point> p) {
    int n = p.size();

    int last = 0;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];
        Point c = p[(i + 2) % n];

        int cur = sign(orient(a, b, c));

        if (cur == 0) {
            continue;
        }

        if (last != 0 && cur != last) {
            return false;
        }

        last = cur;
    }

    return true;
}

Нүкте polygon ішінде ме?

Кез келген polygon үшін ray casting method қолдануға болады.

Идея:

Код: нүкте polygon ішінде

bool insidePolygon(vector<Point> p, Point q) {
    int n = p.size();
    bool inside = false;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        if (onSegment(a, b, q)) {
            return true;
        }

        bool cond1 = (a.y > q.y) != (b.y > q.y);

        if (cond1) {
            double x = a.x + 1.0 * (b.x - a.x) * (q.y - a.y) / (b.y - a.y);

            if (x > q.x) {
                inside = !inside;
            }
        }
    }

    return inside;
}

Векторлар арасындағы бұрыш

Екі вектор арасындағы angle dot product арқылы табылады:

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

Код:

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

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

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

    return acos(cosValue);
}

Нүктені бұру

(x, y) нүктесін координата басы айналасында angle бұрышқа бұру:

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

Код:

struct DPoint {
    double x;
    double y;
};

DPoint rotatePoint(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
    };
}

Integer және double geometry

double үшін EPS

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

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 нөлге тең деп санаймыз.

Базалық geometry template

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};
    }
};

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 dist2(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return dx * dx + dy * dy;
}

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

• екі нүкте арасындағы distance табу
• нүктелер бір түзуде жатыр ма тексеру
• солға немесе оңға бұрылуды анықтау
• segment intersection тексеру
• үшбұрыш area табу
• polygon area табу
• нүкте polygon ішінде ме тексеру
• polygon convex пе тексеру

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

• dot пен cross шатастыру
• cross negative болуы мүмкін екенін ұмыту
• coordinates үлкен кезде int қолдану
• double-ды == арқылы салыстыру
• нүкте segment үстінде жатқан special case ұмыту
• collinear segment-терді өңдемеу
• polygon area ішінде соңғы edge p[n-1] → p[0] ұмыту
• area және екі еселенген area шатастыру

Асимптотика

Қашан не қолданамыз?

Ең бастысы