Cod sursa(job #2875005)

Utilizator Undergamerrotariu dragos Undergamer Data 20 martie 2022 17:12:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <stack>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte
{
    double x,y;
    bool operator <(puncte unu) const{
        return (x<unu.x || (x==unu.x && y<unu.y));
    }
}v[100002];
puncte pct;
int n;
puncte st[100002];
bool produs (puncte a, puncte b, puncte c)
{
    if ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>=0)
        return 1;
    return 0;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort (v+1,v+n+1);
    int vf=1;
    st[0]=v[1];
    st[1]=v[2];
    for (int i=3;i<=n;i++)
    {
        while (vf>0 && produs(st[vf-1],st[vf],v[i])>0)
        {
            vf--;
        }
        st[vf++]=v[i];
    }
    cout<<vf+1<<'\n';
    while (vf>=0)
    {
        cout<<setprecision(9)<<fixed<<st[vf].x<<" "<<st[vf].y<<'\n';
        vf--;
    }
}