Cod sursa(job #3362024)

Utilizator horia_Horia Casuneanu horia_ Data 31 iulie 2026 19:34:41
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;

struct puncte
{
    double x;
    double y;
} v[120005];

void citire()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
}

void detectare()
{
    puncte pmin;
    pmin.x = 1e9;
    pmin.y = 1e9;
    int care;
    for (int i = 1; i <= n; ++i)
    {
        if (v[i].y < pmin.y)
        {
            pmin.y = v[i].y;
            pmin.x = v[i].x;
            care = i;
        }else
        {
            if (v[i].y == pmin.y)
            {
                if (pmin.x > v[i].x)
                {
                    pmin.y = v[i].y;
                    pmin.x = v[i].x;
                    care = i;
                }
            }
        }
    }
    swap(v[1], v[care]);
}

double arie(puncte A, puncte B, puncte C)
{
    A.x -= C.x;
    B.y -= C.y;
    B.x -= C.x;
    A.y -= C.y;
    return A.x * B.y - B.x * A.y;
}

double dist(puncte A, puncte B)
{
    return (A.x-B.x)*(A.x-B.x)
         + (A.y-B.y)*(A.y-B.y);
}

bool cmp(puncte A, puncte B)
{
    double c = arie(v[1], A, B);

    if (c != 0)
        return c > 0;
    return dist(v[1], A) < dist(v[1], B);
}

void sortare()
{
    sort(v + 2, v + n + 1, cmp);
}

void construire()
{
    vector<puncte> stiva;
    stiva.push_back(v[1]);
    stiva.push_back(v[2]);
    for (int i = 3; i <= n; ++i)
    {
        while (stiva.size() >= 2 && arie(stiva[stiva.size() - 2], stiva[stiva.size() - 1], v[i]) <= 0)
            stiva.pop_back();
        stiva.push_back(v[i]);
    }
    fout << stiva.size() << '\n';
    for (int i = 0; i < stiva.size(); ++i)
    {
        fout << stiva[i].x << fixed << setprecision(12) << ' ' << stiva[i].y << fixed << setprecision(12) << '\n';
    }
}

int main()
{
    citire();
    detectare();
    sortare();
    construire();
    return 0;
}