Cod sursa(job #3353308)

Utilizator and_Turcu Andrei and_ Data 5 mai 2026 23:41:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>


using namespace std;


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

struct punct
{
    double x, y;
};

int n;
vector<punct> a;

void citire_punct(punct &a)
{
    fin >> a.x >> a.y;
}

void afis_punct(punct a)
{
    fout << a.x << " " << a.y;
}
bool cmp(punct a, punct b)
{
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double determinant(punct a, punct b, punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int main()
{   
    fin >> n;

    for(int i = 1; i <= n; i++)
    {
        punct x;
        citire_punct(x);

        a.push_back(x);
    }

    sort(a.begin(), a.end(), cmp);

    vector<punct> sus, jos;

    jos.push_back(a[0]);
    jos.push_back(a[1]);
    
    for(int i = 2; i < n; i++)  
    {
        while(jos.size() >= 2 and determinant(jos[jos.size() - 2], jos[jos.size() - 1], a[i]) <= 0)
            jos.pop_back();

        jos.push_back(a[i]);
    }

    
    sus.push_back(a[0]);
    sus.push_back(a[1]);
    
    for(int i = 2; i < n; i++)  
    {
        while(sus.size() >= 2 and determinant(sus[sus.size() - 2], sus[sus.size() - 1], a[i]) >= 0)
            sus.pop_back();
            
        sus.push_back(a[i]);
    }


    fout << fixed << setprecision(12) << jos.size() + sus.size() - 2 << "\n";

    for(int i = 0; i < jos.size(); i++)
    {
        afis_punct(jos[i]);
        fout << "\n";
    }

    // fout << "--\n";

    for(int i = sus.size() - 2; i > 0; i--)
    {
        afis_punct(sus[i]);
        fout << "\n";
    }

    return 0;
}