Cod sursa(job #3355719)

Utilizator coldsh1tANdrei coldsh1t Data 25 mai 2026 10:32:12
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct q
{
    double x, y;
};

q v[120005], st[240005];

bool cmp(q a, q b)
{
    if(a.x<b.x)
    {
        return true;
    }
    else if(a.x>b.x)
    {
        return false;
    }
    else
    {
        if(a.y<b.y)
        {
            return true;
        }
        return false;
    }
}

double arie(q a, q b, q c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}

int main()
{
    long long n;
    fin>>n;

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

    sort(v+1, v+n+1, cmp);

    long long k=0;

    for(int i=1;i<=n;i++)
    {
        while(k>=2 && arie(st[k-1], st[k], v[i])<=0)
        {
            k--;
        }

        st[++k]=v[i];
    }

    long long t=k;

    for(int i=n-1;i>=1;i--)
    {
        while(k>t && arie(st[k-1], st[k], v[i])<=0)
        {
            k--;
        }

        st[++k]=v[i];
    }

    k--;

    fout<<k<<"\n";

    for(int i=1;i<=k;i++)
    {
        fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
    }

    return 0;
}