Cod sursa(job #2477494)

Utilizator ilucianIlea Lucian ilucian Data 20 octombrie 2019 14:38:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct {long double x,y;};
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
punct P[120001];
punct S1[120001];
int k1;
punct S2[120001];
int k2;

/// returneaza 1 daca A este inspre stanga fata de BC
int stanga(punct A, punct B, punct C)
{
    A.x-=B.x;
    A.y-=B.y;
    C.x-=B.x;
    C.y-=B.y;
    long double pv;
    pv=C.x*A.y-C.y*A.x;
    if (pv>0)
        return 1;
    return 0;
}

int cmp(punct A, punct B)
{
    if (A.y<B.y)
        return 1;
    if (A.y>B.y)
        return 0;
    if (A.x<B.x)
        return 1;
    return 0;
}

int main()
{
    fi>>N;
    for (int i=1;i<=N;i++)
        fi>>P[i].x>>P[i].y;
    /// ordonare
    sort(P+1,P+N+1,cmp);
    /// stiva de urcare
    k1=0;
    for (int i=1;i<=N;)
        if (k1<=1)
            S1[++k1]=P[i++];
        else
            if (stanga(P[i],S1[k1-1],S1[k1]))
                S1[++k1]=P[i++];
            else
                k1--;
    /// stiva de coborare
    k2=0;
    for (int i=N;i>=1;)
        if (k2<=1)
            S2[++k2]=P[i--];
        else
            if (stanga(P[i],S2[k2-1],S2[k2]))
                S2[++k2]=P[i--];
            else
                k2--;
    int nrp;
    nrp=k1+k2-2;
    fo<<nrp<<"\n";
    for (int i=1;i<=k1;i++)
        fo<<setprecision(6)<<fixed<<S1[i].x<<" "<<S1[i].y<<"\n";
    for (int i=2;i<=k2-1;i++)
        fo<<setprecision(6)<<fixed<<S2[i].x<<" "<<S2[i].y<<"\n";
    fi.close();
    fo.close();
    return 0;
}