main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
/*
// Structure to represent a 2D point
struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}

    // Check if two points are equal (within a small epsilon)
    bool equals(const Point& other) const {
        const double EPSILON = 1e-9;
        return std::abs(x - other.x) < EPSILON && std::abs(y - other.y) < EPSILON;
    }
};

// Structure to represent a line segment
struct Segment {
    Point start, end;

    Segment(const Point& start, const Point& end) : start(start), end(end) {}
};

// Structure to represent an event in the sweep line algorithm
struct Event {
    Point point;
    bool isStart;      // true if this is the start point of a segment
    int segmentIndex;  // which segment this event belongs to

    Event(const Point& p, bool start, int index)
        : point(p), isStart(start), segmentIndex(index) {}

    // Sort events by x-coordinate, then by y-coordinate
    bool operator<(const Event& other) const {
        if (point.x != other.point.x) {
            return point.x < other.point.x;
        }
        return point.y < other.point.y;
    }
};

// Check if two line segments intersect and return the intersection point
bool findIntersection(const Segment& s1, const Segment& s2, Point& intersection) {
    // Convert line segment to the form ax + by = c
    double a1 = s1.end.y - s1.start.y;
    double b1 = s1.start.x - s1.end.x;
    double c1 = a1 * s1.start.x + b1 * s1.start.y;

    double a2 = s2.end.y - s2.start.y;
    double b2 = s2.start.x - s2.end.x;
    double c2 = a2 * s2.start.x + b2 * s2.start.y;

    double determinant = a1 * b2 - a2 * b1;

    // If lines are parallel
    if (std::abs(determinant) < 1e-9) {
        return false;
    }

    // Find intersection point
    intersection.x = (b2 * c1 - b1 * c2) / determinant;
    intersection.y = (a1 * c2 - a2 * c1) / determinant;

    // Check if intersection point lies on both segments
    auto onSegment = [](const Point& p, const Segment& s) -> bool {
        return p.x >= std::min(s.start.x, s.end.x) && p.x <= std::max(s.start.x, s.end.x) &&
               p.y >= std::min(s.start.y, s.end.y) && p.y <= std::max(s.start.y, s.end.y);
    };

    return onSegment(intersection, s1) && onSegment(intersection, s2);
}

// Check if a point is inside a polygon using ray casting algorithm
bool isPointInPolygon(const Point& point, const std::vector<Point>& polygon) {
    bool inside = false;
    int n = polygon.size();

    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (((polygon[i].y > point.y) != (polygon[j].y > point.y)) &&
            (point.x < (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) /
                               (polygon[j].y - polygon[i].y) + polygon[i].x)) {
            inside = !inside;
        }
    }

    return inside;
}

// Find the intersection of two polygons using sweep line algorithm
std::vector<Point> findPolygonIntersection(const std::vector<Point>& polygonA,
                                           const std::vector<Point>& polygonB) {
    std::vector<Point> result;

    // Convert polygons to segments
    std::vector<Segment> segmentsA, segmentsB;

    for (int i = 0; i < polygonA.size(); i++) {
        segmentsA.push_back(Segment(polygonA[i], polygonA[(i + 1) % polygonA.size()]));
    }

    for (int i = 0; i < polygonB.size(); i++) {
        segmentsB.push_back(Segment(polygonB[i], polygonB[(i + 1) % polygonB.size()]));
    }

    // Find all intersection points
    std::vector<Point> intersectionPoints;

    for (const auto& segA : segmentsA) {
        for (const auto& segB : segmentsB) {
            Point intersection;
            if (findIntersection(segA, segB, intersection)) {
                intersectionPoints.push_back(intersection);
            }
        }
    }

    // Add vertices from polygon A that are inside polygon B
    for (const auto& point : polygonA) {
        if (isPointInPolygon(point, polygonB)) {
            result.push_back(point);
        }
    }

    // Add vertices from polygon B that are inside polygon A
    for (const auto& point : polygonB) {
        if (isPointInPolygon(point, polygonA)) {
            result.push_back(point);
        }
    }

    // Add intersection points
    for (const auto& point : intersectionPoints) {
        result.push_back(point);
    }

    // If we have fewer than 3 points, there's no proper intersection polygon
    if (result.size() < 3) {
        return {};
    }

    // Order the points to form a proper polygon
    // Note: This is a simplified approach; a more robust solution would
    // use a proper polygon construction algorithm

    // Find centroid of points as a reference
    Point centroid{0, 0};
    for (const auto& p : result) {
        centroid.x += p.x;
        centroid.y += p.y;
    }
    centroid.x /= result.size();
    centroid.y /= result.size();

    // Sort points based on angle from centroid
    std::sort(result.begin(), result.end(), [&centroid](const Point& a, const Point& b) {
        double angleA = std::atan2(a.y - centroid.y, a.x - centroid.x);
        double angleB = std::atan2(b.y - centroid.y, b.x - centroid.x);
        return angleA < angleB;
    });

    // Remove duplicate points
    auto newEnd = std::unique(result.begin(), result.end(),
                              [](const Point& a, const Point& b) { return a.equals(b); });
    result.erase(newEnd, result.end());

    return result;
}

// Function to print a polygon
void printPolygon(const std::vector<Point>& polygon) {
    std::cout << "Polygon with " << polygon.size() << " vertices:" << std::endl;
    for (const auto& p : polygon) {
        std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
    }
}

int main() {
    // Example: find the intersection of two polygons

    // First polygon: a rectangle
    std::vector<Point> polygonA = {
        {32, 8}, {14, 6}, {24, 26}
    };

    // Second polygon: another rectangle that overlaps with the first
    std::vector<Point> polygonB = {
        {24, 4}, {30, 22}, {12, 20}
    };

    std::cout << "Finding intersection of two polygons..." << std::endl;

    std::vector<Point> intersection = findPolygonIntersection(polygonA, polygonB);

    if (intersection.empty()) {
        std::cout << "No intersection found." << std::endl;
    } else {
        printPolygon(intersection);
    }

    return 0;
}
*/



using namespace std;

// Punktstruktur
struct Point {
    double x, y;
};

// Hilfsfunktion: Orientierungstest
// >0 = links, <0 = rechts, =0 kollinear
static double orient(const Point &a, const Point &b, const Point &c) {
    return (b.x - a.x)*(c.y - a.y)
         - (b.y - a.y)*(c.x - a.x);
}

// Wir merken uns, ob der Punkt aus der linken oder rechten Kette stammt
struct ChainPoint {
    const Point* pt;
    bool isLeft;
};

// Einfache Darstellung einer Diagonale als Paar von Point-Zeigern
using Diagonal = pair<const Point*, const Point*>;

// Triangulation
vector<Diagonal> triangulationMonotonePolygon(
    const vector<Point>& leftChain,
    const vector<Point>& rightChain)
{
    int nL = leftChain.size(), nR = rightChain.size();
    int n  = nL + nR;

    // 1) Mische und sortiere nach y absteigend
    vector<ChainPoint> A;
    A.reserve(n);
    for (auto &p : leftChain)  A.push_back({&p, true});
    for (auto &p : rightChain) A.push_back({&p, false});
    sort(A.begin(), A.end(), [&](auto &a, auto &b){
        return a.pt->y > b.pt->y;
    });

    // 2) Stack initialisieren mit ersten beiden
    vector<ChainPoint> S;
    S.reserve(n);
    S.push_back(A[0]);
    S.push_back(A[1]);

    vector<Diagonal> diagonals;
    diagonals.reserve(n-3);

    // 3) Hauptschleife über A[2..n-1]
    for (int i = 2; i < n; ++i) {
        auto &curr = A[i];
        // Fall 1: unterschiedliche Ketten
        if (curr.isLeft != S.back().isLeft) {
            // Pop alle bis auf den Stack-Boden
            while (S.size() > 1) {
                diagonals.emplace_back(S.back().pt, curr.pt);
                S.pop_back();
            }
            // Jetzt ist nur noch der Boden in S
            // Push vorherigen und current
            S.pop_back();
            S.push_back(A[i-1]);
            S.push_back(curr);
        }
        else {
            // Fall 2: gleiche Kette
            // Pop so lange, wie die Ecke keine konvexe Verbindung bildet
            while (S.size() > 1) {
                auto &top1 = S.back();
                auto &top2 = S[S.size()-2];
                double o = orient(*top2.pt, *top1.pt, *curr.pt);
                // Für linke Kette wollen wir linksgewinkelt (o > 0),
                // für rechte Kette rechtsgewinkelt (o < 0)
                if ((curr.isLeft && o > 0) ||
                    (!curr.isLeft && o < 0))
                {
                    diagonals.emplace_back(top2.pt, curr.pt);
                    S.pop_back();
                } else {
                    break;
                }
            }
            S.push_back(curr);
        }
    }

    // 4) Abschluss: verbinde restliche Stack-Punkte mit dem letzten
    // Nun sind S[0]..S[m-1] verblieben; wir müssen S[1..m-2] mit S[m-1] diagonal verbinden
    auto &last = S.back();
    for (int j = 1; j+1 < (int)S.size(); ++j) {
        diagonals.emplace_back(S[j].pt, last.pt);
    }

    return diagonals;
}

// --- Beispiel und Test ---
int main(){
    // Beispiel y-monotones Polygon (CCW):
    // Linke Kette von oben nach unten:
    vector<Point> L = {{0,10},{-5,5},{-4,0},{-3,-5},{0,-10}};
    // Rechte Kette von oben nach unten:
    vector<Point> R = {{0,10},{4,5},{6,0},{3,-5},{0,-10}};

    const std::vector<Point> leftChain = {{-6,10}, {-6, 4}, {-8, 2}, {-6, -4}};
    const std::vector<Point> rightChain = {{2, 8}, {2, 7}, {2, 6}, {4, 0.85}, {2, -2}, {6, -6}};
    auto diags = triangulationMonotonePolygon(leftChain, rightChain);
    cout << "Diagonalen (n-3 = " << diags.size() << "):\n";
    for (auto &d : diags) {
        cout << "(" << d.first->x << "," << d.first->y << ")"
             << " - "
             << "(" << d.second->x << "," << d.second->y << ")\n";
    }
}