Cod sursa(job #3216313)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 15 martie 2024 21:00:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define s second
#define f first
const int NMAX=120000+5;

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

typedef long double ld;
typedef pair<ld, ld> pld;

ld det(pld, pld, pld);
bool cmp(pld, pld);

pld v[NMAX], st[NMAX];
int n;
ld aria;

signed main()
{
    int i, poz=1, cnt=0;
    pld minim={1e9, 1e9};
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>v[i].f>>v[i].s;
        if(minim.s>v[i].s)
        {
            minim=v[i];
            poz=i;
        }
        else if(minim.s==v[i].s && minim.f>v[i].f)
        {
            minim=v[i];
            poz=i;
        }
    }
    swap(v[poz], v[1]);
    sort(v+2, v+n+1, cmp);
    st[++cnt]=v[1];
    st[++cnt]=v[2];
    for(i=3; i<=n; i++)
    {
        while(cnt>=2 && det(v[i], st[cnt-1], st[cnt])>0)
            cnt--;
        st[++cnt]=v[i];
    }
    cout<<cnt<<'\n';
    for(i=cnt; i>=1; i--) cout<<fixed<<setprecision(6)<<st[i].f<<' '<<st[i].s<<'\n';
    return 0;
}

bool cmp(pld a, pld b)
{
    return det(b, v[1], a)<0;
}

ld det(pld a, pld b, pld c)
{
    return a.f*(b.s-c.s)-a.s*(b.f-c.f)+(b.f*c.s-b.s*c.f);
}