Cod sursa(job #2756355)

Utilizator bogikanagyNagy Boglarka bogikanagy Data 31 mai 2021 11:03:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#define ll long long
#define Kicsi 1e-12
#define Nagy 1<<30

using namespace std;

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

ll n,m,i,j,poz;
struct pont
{
    double x,y;
};
vector <pont> x;
pont akt={0,Nagy};
bool rendez (pont a, pont b)
{
    double p=(a.x-akt.x)*(b.y-akt.y)-(b.x-akt.x)*(a.y-akt.y);
    return p>Kicsi;
}

bool fordul (pont a, pont b, pont c)
{
    double p=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    return p>Kicsi;
}

int main()
{
    cin>>n;
    vector <pont> x(n+1);
    for (i=1;i<=n;++i)
    {
        cin>>x[i].x>>x[i].y;
        if (x[i].y<akt.y)
        {
            akt=x[i];
            poz=i;
        }
        else if (x[i].y==akt.y && x[i].x<akt.x)
        {
            akt=x[i];
            poz=i;
        }
    }

    x[poz]=x[1];
    x[1]=akt;
    sort(x.begin()+2,x.end(),rendez);
    x.push_back(x[1]);

    vector <pont> v(n+5);
    v[1]=x[1];
    v[2]=x[2];
    i=2;
    ll db=2;
    for (i=3;i<=n+1;++i)
    {
        while (db>=2&&!fordul(v[db-1],v[db],x[i])) db--;

        db++;
        v[db]=x[i];
    }

    cout<<db-1<<"\n";
    for (i=1;i<db;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}