Cod sursa(job #3288968)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 25 martie 2025 00:28:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef pair <double, double> Point;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

double cross_product(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);
}

vector < Point > convexHull(vector < Point >& points) {
    // Pas 1. Sortarea punctelor
    Point p0 = points[0];
    int poz = 0;
    for (int32_t i = 1; i < points.size(); i++) {
        if (points[i] < p0)
            p0 = points[i], poz = i;

    }
    swap(points[0], points[poz]);

    // p[0], a, b
    sort(points.begin() + 1, points.end(), [&points](const Point &a, const Point &b) {
        const double cp = cross_product(points[0], a, b);
        if (cp == 0)
            return (points[0].x-a.x)*(points[0].x-a.x) + (points[0].y-a.y)*(points[0].y-a.y) < (points[0].x-b.x)*(points[0].x-b.x) + (points[0].y-b.y)*(points[0].y-b.y);
        return cp < 0;
    });

    // Pas 2. Determinarea punctelor de pe infasuratoarea convexa

    vector < Point > ch;
    ch.push_back(points[0]);
    ch.push_back(points[1]);

    for (int32_t i = 2; i < points.size(); i++) {
        while (ch.size() > 1 && cross_product(ch[ch.size() - 2], ch[ch.size() - 1], points[i]) >= 0) {
            ch.pop_back();
        }
        ch.push_back(points[i]);
    }

    return ch;
}

int main() {
    int32_t N;
    fin >> N;
    vector<Point> points(N);

    for (auto &p : points) {
        fin >> p.x >> p.y;
    }

    // Varianta 2 - Convex Hull bazat pe Graham Scan (cu tratare caz cand punctul de start e coliniar) + Brute force
    auto ch = convexHull(points);

    reverse(ch.begin(), ch.end());

    fout << ch.size() << '\n';
    fout << setprecision(12) << fixed;
    for (auto &p : ch) {
        fout << p.x << ' ' << p.y << '\n';
    }
}