Cod sursa(job #2214087)

Utilizator VladTZYVlad Tiganila VladTZY Data 18 iunie 2018 13:14:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int n,i,k,pmin;
struct hh{
    double x,y;
};
hh a[120050];
double panta(hh a,hh b)
{
    return (b.y-a.y)/(b.x-a.x);
}
bool cmp(hh p,hh t)
{
    if(panta(a[1],p)<panta(a[1],t))
        return 1;
    else
        return 0;
}
int s[120050];
int main()
{
    f>>n;
    f>>a[1].x>>a[1].y;
    pmin=1;
    for(i=2;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
        if(a[i].x<a[pmin].x)
            pmin=i;
        else
            if(a[i].x==a[pmin].x)
                if(a[i].y<a[pmin].y)
                    pmin=i;

    }
    swap(a[pmin],a[1]);
    sort(a+2,a+1+n,cmp);
    k=2;
    s[1]=1;
    s[2]=2;
    for(i=3;i<=n;i++)
    {
        if(k==2)
        {
            k++;
            s[k]=i;
        }
        else
        {
            while(k>2&&panta(a[s[k-1]],a[i])<panta(a[s[k-1]],a[s[k]]))
                k--;
            k++;
            s[k]=i;
        }
    }
    g<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        g<<setprecision(13)<<fixed<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
    }
    return 0;
}