Cod sursa(job #2168061)

Utilizator andrei32576Andrei Florea andrei32576 Data 14 martie 2018 09:24:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

int n,i,k;
struct punct
{
    double x,y;
};
punct v[120005],H[120005];


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

bool cmp(punct a,punct b)
{
    if(a.x<b.x) return 1;
    if(a.x==b.x && a.y<b.y) return 1;
    return 0;
}

double semn(punct A,punct B,punct O)
{
    return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}

void hull()
{
    for(i=1;i<=n;i++)
    {
        while(k>=2 && semn(H[k-1],H[k],v[i])<=0) k--;
        H[++k]=v[i];
    }


    int kk=k+1;
    for(i=n;i>=1;i--)
    {
        while(k>=kk && semn(H[k-1],H[k],v[i])<=0) k--;
        H[++k]=v[i];
    }

    k--;

}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,cmp);

    hull();

    g<<k<<"\n";
    for(i=1;i<=k;i++)
        g<<fixed<<setprecision(12)<<H[i].x<<" "<<H[i].y<<"\n";

    f.close();
    g.close();
    return 0;
}