Cod sursa(job #2003985)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 24 iulie 2017 15:38:12
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#define NM 100005
#define COR 1005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct {double x, y, u;} V[NM], Stiva[NM];
int n, vf;

inline double dir(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

bool comp(punct a, punct b)
{
    return dir(V[1], a, b)>0;
}

void citeste()
{
    int i, nod;
    float minim=COR;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>V[i].x>>V[i].y;
        if (V[i].y<minim)
        {
            minim=V[i].y;
            nod=i;
        }
    }
    swap(V[1], V[nod]);
}

void GrahamScan()
{
    int i;
    Stiva[1]=V[1];
    Stiva[2]=V[2];
    V[n+1]=V[1];
    vf=2;
    for (i=3; i<=n+1; i++)
    {
        while (dir(Stiva[vf-1], Stiva[vf], V[i])<0 && vf>1)
        {
            vf--;
        }
        vf++;
        Stiva[vf]=V[i];
    }
}

int main()
{
    int i;
    citeste();
    sort(V+2, V+n+1, comp);

    GrahamScan();

    fout<<--vf<<'\n';

    for (i=1; i<=vf; i++)
        fout<<Stiva[i].x<<" "<<Stiva[i].y<<'\n';
    return 0;
}