Cod sursa(job #2521188)

Utilizator daru06Daria Culac daru06 Data 10 ianuarie 2020 15:18:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define maxn 120000
#define INF 1000000000

using namespace std;

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

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

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]);
}

int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>X[i]>>Y[i];
    pctin=0;
    X[0]=INF;
    Y[0]=INF;
    for(int i=1;i<=n;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[++k]=i;
    sort(IND+1, IND+k+1, cmp);
    ST[1]=pctin;
    p=1;
    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;
}