📐 Основи на Изчислителната Геометрия

Геометрията е една от най-предизвикателните теми в състезателното програмиране заради работата с числа с плаваща запетая (double) и граничните случаи. Тази тема изисква прецизно разбиране на математическите концепции, внимание към детайлите и познаване на често срещаните грешки при работа с геометрични задачи.

1. Точки и Вектори

1.1. Основни Дефиниции

Точка \(P(x, y)\) и вектор \(\vec{v}(x, y)\) се представят еднакво в паметта, но имат различен математически и геометричен смисъл:

• Точка: Представлява конкретна позиция в двумерното пространство с координати \((x, y)\).
• Вектор: Представлява посока и големина (магнитуд). Векторът се дефинира като разликата между две точки: \(\vec{AB} = B - A\).

1.2. Пълна Имплементация на Структура Point

struct Point {
    long long x, y; // Използвайте long long винаги, когато е възможно!

    // Конструктори
    Point() : x(0), y(0) {}
    Point(long long x, long long y) : x(x), y(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}; 
    }

    // Сравнение (за сортиране)
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }

    // Дължина на вектора (квадрат, за да избегнем sqrt)
    long long lengthSq() const {
        return x * x + y * y;
    }
};

1.3. Основни Операции с Вектори

// Разстояние между две точки (квадрат)
long long distSq(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// Евклидово разстояние (само ако е необходимо)
double dist(Point a, Point b) {
    return sqrt(distSq(a, b));
}

// Манхатън разстояние
long long manhattan(Point a, Point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

2. Скаларно Произведение (Dot Product)

2.1. Математическа Дефиниция

Скаларното произведение на два вектора \(A\) и \(B\) се дефинира като: $\(A \cdot B = x_A x_B + y_A y_B = |A| |B| \cos \theta\)$

където \(\theta\) е ъгълът между двата вектора.

2.2. Геометрични Свойства

• Ако \(A \cdot B > 0\): Ъгълът \(\theta\) е остър (\(< 90^\circ\)).
• Ако \(A \cdot B = 0\): Векторите са перпендикулярни (ортогонални).
• Ако \(A \cdot B < 0\): Ъгълът \(\theta\) е тъп (\(> 90^\circ\)).

2.3. Приложения

Проекция на вектор: Проекцията на вектор \(A\) върху вектор \(B\) е: $\(\text{proj}_B A = \frac{A \cdot B}{|B|^2} \cdot B\)$

Намиране на ъгъл между вектори: $\(\cos \theta = \frac{A \cdot B}{|A| |B|}\)$

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

// Ъгъл между два вектора (в радиани)
double angle(Point a, Point b) {
    return acos(dot(a, b) / (sqrt(a.lengthSq()) * sqrt(b.lengthSq())));
}

// Проверка дали два вектора са перпендикулярни
bool isPerpendicular(Point a, Point b) {
    return dot(a, b) == 0;
}

3. Векторно Произведение (Cross Product)

3.1. Математическа Дефиниция

В 2D векторното произведение е скаларна стойност (в 3D е вектор): $\(A \times B = x_A y_B - x_B y_A = |A| |B| \sin \theta\)$

където \(\theta\) е ъгълът между двата вектора.

3.2. Геометрични Свойства

• Геометрично значение: Ориентираното лице на успоредника, образуван от векторите \(A\) и \(B\).
• Лице на триъгълник с върхове \((0,0), A, B\): \(\frac{|A \times B|}{2}\).
• Знак:
  • Положителен: \(B\) е отляво на \(A\) (обратно на часовника - CCW)
  • Отрицателен: \(B\) е отдясно на \(A\) (по часовника - CW)
  • Нула: векторите са колинеарни (паралелни)

3.3. Имплементация и Приложения

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

// Лице на триъгълник ABC (може да е отрицателно)
long long triangleArea2(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

// Абсолютно лице на триъгълник
long long absTriangleArea2(Point a, Point b, Point c) {
    return abs(triangleArea2(a, b, c));
}

// Лице на многоъгълник със Shoelace формула
long long polygonArea2(const vector<Point>& poly) {
    long long area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += cross(poly[i], poly[j]);
    }
    return abs(area);
}

4. Ориентация на Три Точки (CCW Test)

4.1. Основна Концепция

Къде се намира точка \(C\) спрямо ориентираната права \(\overrightarrow{AB}\)?

Използваме векторното произведение на \(\vec{AB}\) и \(\vec{AC}\): $\(\text{orient}(A, B, C) = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)\)$

4.2. Интерпретация на Резултата

• \(\text{orient}(A,B,C) > 0\): \(C\) е вляво от \(\overrightarrow{AB}\) (обратно на часовника - CCW).
• \(\text{orient}(A,B,C) < 0\): \(C\) е вдясно от \(\overrightarrow{AB}\) (по часовника - CW).
• \(\text{orient}(A,B,C) = 0\): Точките \(A, B, C\) са колинеарни (лежат на една права).

4.3. Имплементация

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

// Проверка дали точка лежи на отсечка
bool onSegment(Point a, Point b, Point c) {
    // Първо проверяваме дали са колинеарни
    if (orient(a, b, c) != 0) return false;

    // После проверяваме дали c е между a и b
    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}

5. Разстояния и Метрики

5.1. Евклидово Разстояние

Класическото разстояние между две точки в равнината: $\(d(P_1, P_2) = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\)$

Важно: Винаги използвайте квадрата на разстоянието при сравнения, за да избегнете операцията sqrt и грешки с плаваща запетая!

5.2. Манхатън Разстояние

Разстоянието, измерено по хоризонтални и вертикални линии (като в уличната мрежа): $\(d_M(P_1, P_2) = |x_1-x_2| + |y_1-y_2|\)$

5.3. Разстояние от Точка до Права

За да намерим разстоянието от точка \(P\) до права, минаваща през точки \(A\) и \(B\):

\[d = \frac{|\text{orient}(A, B, P)|}{|AB|}\]

// Разстояние от точка до права (като квадрат за точност)
long long distToLineSq(Point p, Point a, Point b) {
    long long num = abs(orient(a, b, p));
    long long den = distSq(a, b);
    // Връщаме num^2 / den за да избегнем double
    return (num * num) / den;
}

// Разстояние от точка до отсечка
double distToSegment(Point p, Point a, Point b) {
    if (a == b) return dist(p, a);

    Point ab = b - a;
    Point ap = p - a;

    // Проекция на ap върху ab
    long long t = dot(ap, ab);

    if (t <= 0) return dist(p, a);  // Най-близка до a

    long long abLen = ab.lengthSq();
    if (t >= abLen) return dist(p, b);  // Най-близка до b

    // Перпендикулярна проекция
    return abs(cross(ab, ap)) / sqrt(abLen);
}

6. Пресичане на Отсечки

6.1. Общ Случай

Две отсечки \(AB\) и \(CD\) се пресичат, ако: 1. Точките \(C\) и \(D\) са от различни страни на правата \(AB\), И 2. Точките \(A\) и \(B\) са от различни страни на правата \(CD\).

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 (o1 * o2 < 0 && o3 * o4 < 0) return true;

    // Специални случаи - колинеарни точки
    if (o1 == 0 && onSegment(a, b, c)) return true;
    if (o2 == 0 && onSegment(a, b, d)) return true;
    if (o3 == 0 && onSegment(c, d, a)) return true;
    if (o4 == 0 && onSegment(c, d, b)) return true;

    return false;
}

6.2. Намиране на Точката на Пресичане

// Намиране на точка на пресичане (с double за точност)
pair<double, double> intersectionPoint(Point a, Point b, Point c, Point d) {
    double a1 = b.y - a.y;
    double b1 = a.x - b.x;
    double c1 = a1 * a.x + b1 * a.y;

    double a2 = d.y - c.y;
    double b2 = c.x - d.x;
    double c2 = a2 * c.x + b2 * c.y;

    double det = a1 * b2 - a2 * b1;

    double x = (b2 * c1 - b1 * c2) / det;
    double y = (a1 * c2 - a2 * c1) / det;

    return {x, y};
}

7. Многоъгълници

7.1. Проверка Дали Точка е Вътре в Многоъгълник

Метод на Ray Casting: Пускаме лъч от точката надясно и броим пресичанията с ръбовете. Ако са нечетен брой, точката е вътре.

bool pointInPolygon(Point p, const vector<Point>& poly) {
    int n = poly.size();
    int count = 0;

    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;

        // Проверяваме дали лъчът пресича ръба poly[i]-poly[j]
        if ((poly[i].y <= p.y && p.y < poly[j].y) ||
            (poly[j].y <= p.y && p.y < poly[i].y)) {

            // Изчисляваме x-координата на пресичането
            long long x = poly[i].x + 
                (p.y - poly[i].y) * (poly[j].x - poly[i].x) / 
                (poly[j].y - poly[i].y);

            if (p.x < x) count++;
        }
    }

    return count % 2 == 1;
}

7.2. Проверка Дали Многоъгълник е Изпъкнал

Многоъгълникът е изпъкнал, ако всички завои са в една посока (всички CCW или всички CW).

bool isConvex(const vector<Point>& poly) {
    int n = poly.size();
    if (n < 3) return false;

    int sign = 0;
    for (int i = 0; i < n; i++) {
        long long o = orient(poly[i], poly[(i+1)%n], poly[(i+2)%n]);

        if (o != 0) {
            if (sign == 0) sign = (o > 0) ? 1 : -1;
            else if ((o > 0 ? 1 : -1) != sign) return false;
        }
    }
    return true;
}

8. Convex Hull (Изпъкнала Обвивка)

8.1. Алгоритъм на Graham Scan

Този алгоритъм намира изпъкналата обвивка на множество от точки с времева сложност \(O(n \log n)\).

// Намиране на изпъкнала обвивка с Graham Scan
vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points;

    // Намираме най-долната точка (при равенство - най-лявата)
    int minIdx = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[minIdx].y || 
            (points[i].y == points[minIdx].y && points[i].x < points[minIdx].x)) {
            minIdx = i;
        }
    }
    swap(points[0], points[minIdx]);
    Point pivot = points[0];

    // Сортираме по полярен ъгъл спрямо pivot
    sort(points.begin() + 1, points.end(), [&](Point a, Point b) {
        long long o = orient(pivot, a, b);
        if (o == 0) {
            // Колинеарни - по-близката първа
            return distSq(pivot, a) < distSq(pivot, b);
        }
        return o > 0;
    });

    // Строим hull
    vector<Point> hull;
    for (Point p : points) {
        // Премахваме точки, които правят десен завой
        while (hull.size() > 1 && 
               orient(hull[hull.size()-2], hull[hull.size()-1], p) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }

    return hull;
}

8.2. Алгоритъм на Andrew (Monotone Chain)

По-прост и по-стабилен алгоритъм със същата сложност \(O(n \log n)\).

vector<Point> convexHullAndrew(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points;

    sort(points.begin(), points.end());

    // Строим долната част на hull
    vector<Point> lower;
    for (int i = 0; i < n; i++) {
        while (lower.size() >= 2 && 
               orient(lower[lower.size()-2], lower[lower.size()-1], points[i]) <= 0) {
            lower.pop_back();
        }
        lower.push_back(points[i]);
    }

    // Строим горната част на hull
    vector<Point> upper;
    for (int i = n - 1; i >= 0; i--) {
        while (upper.size() >= 2 && 
               orient(upper[upper.size()-2], upper[upper.size()-1], points[i]) <= 0) {
            upper.pop_back();
        }
        upper.push_back(points[i]);
    }

    // Премахваме последните точки (дублирани)
    lower.pop_back();
    upper.pop_back();

    // Обединяваме двете части
    lower.insert(lower.end(), upper.begin(), upper.end());
    return lower;
}

9. Практически Приложения

9.1. Определяне на Вида на Триъгълник

string triangleType(Point a, Point b, Point c) {
    long long ab = distSq(a, b);
    long long bc = distSq(b, c);
    long long ca = distSq(c, a);

    // Проверка дали е правоъгълен (Питагорова теорема)
    if (ab + bc == ca || bc + ca == ab || ca + ab == bc) {
        return "Правоъгълен";
    }

    // Проверка чрез скаларно произведение
    Point ab_vec = b - a, ac_vec = c - a;
    long long d1 = dot(ab_vec, ac_vec);

    if (d1 < 0) return "Тъпоъгълен";
    if (d1 > 0) return "Остроъгълен";

    return "Правоъгълен";
}

9.2. Намиране на Центъра на Тежестта

Point centroid(const vector<Point>& poly) {
    long long cx = 0, cy = 0;
    long long area = 0;
    int n = poly.size();

    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        long long cross_prod = cross(poly[i], poly[j]);
        area += cross_prod;
        cx += (poly[i].x + poly[j].x) * cross_prod;
        cy += (poly[i].y + poly[j].y) * cross_prod;
    }

    area /= 2;
    cx /= (6 * area);
    cy /= (6 * area);

    return Point(cx, cy);
}

10. Гранични Случаи и Често Срещани Грешки

10.1. Гранични Случаи

1. Колинеарни точки: Винаги проверявайте случая, когато три точки лежат на една права.
2. Вертикални/хоризонтални линии: Внимавайте с деление на нула.
3. Съвпадащи точки: Проверявайте дали две точки са идентични.
4. Дегенерирани многоъгълници: Многоъгълник с площ 0 или с по-малко от 3 върха.

10.2. Числова Стабилност

// Константа за сравнение на double стойности
const double EPS = 1e-9;

// Безопасно сравнение
bool equals(double a, double b) {
    return abs(a - b) < EPS;
}

bool lessOrEqual(double a, double b) {
    return a < b + EPS;
}

10.3. Overflow при Cross Product

Когато координатите са до \(10^9\), векторното произведение може да достигне \(10^{18}\), което влиза в long long. Но при по-големи стойности или при множество операции внимавайте за overflow!

// Ако координатите са много големи, използвайте __int128
__int128 safeCross(Point a, Point b) {
    return (__int128)a.x * b.y - (__int128)a.y * b.x;
}

11. Задачи за Упражнение

11.1. Основни Задачи

1. Codeforces 1C - Ancient Berland Circus: Намиране на площта на най-малкия правилен многоъгълник, който съдържа три дадени точки като върхове. (Лица и радиуси на описана окръжност)

2. UVa 191 - Intersection: Проверка дали отсечка пресича правоъгълник. (Пресичане на отсечки и точка в многоъгълник)

3. Codeforces 166B - Polygons: Проверка дали един многоъгълник е изцяло вътре в друг. (Изпъкнали многоъгълници)

11.2. Convex Hull Задачи

1. SPOJ - BSHEEP: Намиране на изпъкналата обвивка и изчисляване на периметъра ѝ.

2. Codeforces 685B - Kay and Snowflake: Работа с центроиди на дървета от многоъгълници.

3. UVa 11265 - The Sultan's Problem: Сечение на изпъкнали многоъгълници.

11.3. Напреднали Задачи

1. Codeforces 769C - Cycle: Намиране на цикъл в граф с използване на геометрични свойства.

2. SPOJ - CLOSEST: Намиране на най-близката двойка точки (Divide and Conquer с геометрия).

3. IOI 2013 - Art Class: Класификация на картини със стойности на геометрични параметри.

4. BOI 2007 - Sound: Пресичане на отсечки с ъгли и разстояния.

12. Съвети за Успех

12.1. Избягване на Числа с Плаваща Запетая

1. Използвайте long long винаги, когато е възможно. Векторно произведение, скаларно произведение и ориентация могат да се изчисляват с цели числа.

2. Сравнявайте квадрати на разстояния вместо самите разстояния:

   // Лошо
   if (dist(a, b) < dist(c, d)) { ... }
   
   // Добре
   if (distSq(a, b) < distSq(c, d)) { ... }
   

3. Избягвайте sqrt когато е възможно.

12.2. Работа с Double (когато е неизбежно)

1. Винаги използвайте EPS за сравнение:

   const double EPS = 1e-9;
   if (abs(a - b) < EPS) { // Равни са }
   

2. Внимавайте с деление:

   // Проверете за нула преди деление
   if (abs(denominator) > EPS) {
       result = numerator / denominator;
   }
   

3. Използвайте long double за по-голяма точност при нужда.

12.3. Дебъгване на Геометрични Задачи

1. Визуализирайте: Нарисувайте точките и фигурите на хартия или използвайте графичен инструмент.

2. Тествайте с малки примери: Започнете с триъгълници и квадрати преди да минете към сложни многоъгълници.

3. Проверявайте граничните случаи:

   • Колинеарни точки
   • Вертикални и хоризонтални линии
   • Съвпадащи точки
   • Дегенерирани фигури (площ 0)

4. Проверявайте знаците: При векторно произведение знакът има значение!

12.4. Оптимизация

1. Предварителни изчисления: Ако използвате едни и същи разстояния/ъгли многократно, изчислете ги предварително.

2. Избягвайте скъпи операции: sqrt, sin, cos, atan2 са бавни. Използвайте ги само когато е необходимо.

3. Използвайте подходящи структури от данни: За проверка на много точки в многоъгълник, разгледайте по-бързи методи като триангулация.

🏁 Финални Съвети

✅ Направете: - Използвайте long long за координати - Сравнявайте квадрати на разстояния - Тествайте граничните случаи - Проверявайте ориентацията на точки - Визуализирайте задачата

❌ Избягвайте: - double без EPS при сравнения - Излишно използване на sqrt - Забравяне на колинеарни случаи - Overflow при големи координати - Деление на нула

Полезни Формули за Справка

Площи: - Триъгълник: \(\frac{|cross(AB, AC)|}{2}\) - Многоъгълник (Shoelace): \(\frac{1}{2}|\sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i)|\)

Разстояния: - Евклидово: \(\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\) - Манхатън: \(|x_1-x_2| + |y_1-y_2|\) - Точка до права: \(\frac{|ax_0 + by_0 + c|}{\sqrt{a^2 + b^2}}\)

Векторни операции: - Dot product: \(A \cdot B = |A||B|\cos\theta\) - Cross product: \(A \times B = |A||B|\sin\theta\) - Дължина: \(|A| = \sqrt{x^2 + y^2}\)

Успех на олимпиадите! 🚀