Cod sursa(job #3333577)

Utilizator stefdani1Danaila Stefan-Alexandru stefdani1 Data 14 ianuarie 2026 12:06:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const int MAXN = 120005;
const double EPS = 1e-12;

struct Punct
{
    double x, y;
};

Punct p[MAXN];      // Vectorul cu toate punctele
Punct hull[MAXN];   // Vectorul cu punctele de pe înfășurătoare
int n;              // Numărul total de puncte
int k;              // Numărul de puncte de pe înfășurătoare
Punct origine;

// Produsul vectorial
double produs(Punct A, Punct B, Punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

// Distanța la pătrat
double dist2(Punct A, Punct B)
{
    double dx = B.x - A.x;
    double dy = B.y - A.y;
    return dx * dx + dy * dy;
}

// Comparator pentru sortare
bool cmp(Punct A, Punct B)
{
    double c = produs(origine, A, B);
    if (fabs(c) < EPS)
        return dist2(origine, A) < dist2(origine, B);
    return c > 0;
}

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

    fout << fixed << setprecision(6);

    // Citim punctele
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> p[i].x >> p[i].y;

    // Găsim punctul cel mai de jos
    int start = 0;
    for (int i = 1; i < n; i++)
    {
        if (p[i].y < p[start].y - EPS || (fabs(p[i].y - p[start].y) < EPS && p[i].x < p[start].x))
            start = i;
    }

    swap(p[0], p[start]);
    origine = p[0];

    // Sortăm punctele după unghi
    sort(p + 1, p + n, cmp);

    // Construim înfășurătoarea folosind vectorul hull
    hull[0] = p[0];
    hull[1] = p[1];
    k = 2;

    for (int i = 2; i < n; i++)
    {
        while (k > 1 && produs(hull[k-2], hull[k-1], p[i]) < EPS)
        {
            k = k - 1;
        }
        hull[k] = p[i];
        k = k + 1;
    }

    // Afișăm înfășurătoarea
    fout << k << "\n";
    for (int i = 0; i < k; i++)
    {
        fout << hull[i].x << " " << hull[i].y << "\n";
    }

    return 0;
}