Cod sursa(job #2520457)

Utilizator daru06Daria Culac daru06 Data 9 ianuarie 2020 14:18:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 120000
#define INF 1000000000
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

double X[maxn], Y[maxn];
int ST[maxn], IND[maxn], pctin,l, n,p;

bool cmp(int a, int b)
{
    return (X[a]-X[pctin]) * (Y[b]-Y[pctin]) > (Y[a]-Y[pctin]) * (X[b]-X[pctin]);
}

double semn(int i1, int i2, int i3)
{
    return (X[i1]*Y[i2] + X[i2]*Y[i3] + X[i3]*Y[i1] - X[i3]*Y[i2] - X[i1]*Y[i3] - X[i2]*Y[i1])/2;
}

int main()
{
    f>>n;
    X[0]=INF;
    Y[0]=INF;
    pctin=0;
    for(int i=1;i<=n;i++)
    {
        f>>X[i]>>Y[i];
        if(Y[i] < Y[pctin])
            pctin=i;
        else
        if(Y[i]==Y[pctin])
            if(X[i]<X[pctin])
                pctin=i;
    }
    for(int i=1;i<=n;i++)
        if(i!=pctin)
            IND[++l]=i;
    sort(IND+1, IND+n, cmp);
    p=1;
    ST[1]=pctin;
    for(int i=1;i<=n-1;i++)
    {
        while(p>=2 and semn(ST[p-1], ST[p], IND[i])<0)
            p--;
        ST[++p]=IND[i];
    }
    g<<p<<'\n';
    for(int i=1;i<=p;i++)
        g<<fixed<<setprecision(6)<<X[ST[i]]<<" "<<Y[ST[i]]<<'\n';
    f.close();
    g.close();
    return 0;
}