Cod sursa(job #2351242)

Utilizator Eduard24Eduard Scaueru Eduard24 Data 22 februarie 2019 09:20:58
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 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)<=0) k--;
        H[++k]=v;
    }


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

    k--;

}

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

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

    hull();

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

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