Cod sursa(job #2047507)

Utilizator rangal3Tudor Anastasiei rangal3 Data 24 octombrie 2017 21:57:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define file "infasuratoare"
#define N 120003

using namespace std;

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

int n;
int stiva[N],len;
bool viz[N];

struct punct{
    float x,y;
} A[N];

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

inline double plan(punct a,punct b,punct p) //returneaza + daca p se afla in planul pozitiv al dreptei (a,b), - daca este in planul negativ
//si 0 daca este pe dreapta. punctul poate fi adaugat doar daca se afla in planul pozitiv al dreptei.
{
    return -( (p.x - a.x)*(b.y-a.y) + (a.y - p.y)*(b.x-a.x) ); //in functie de ecuatia dreptei.
}


void citire()
{
    fin>>n;
    for(int i=1; i<=n; ++i)
        fin>>A[i].x>>A[i].y;
}

void Graham()
{
    sort(A+1,A+n+1,cmp);

    len = 2;
    stiva[1] = 1;
    stiva[2] = 2;
    viz[2] = 1;

    for(int i=3; i<=n; ++i)
    {
        while(len > 1 && plan(A[stiva[len-1]],A[stiva[len]],A[i]) <= 0)
              viz[stiva[len]] = 0, --len; // scoatem elementul din stiva.

        stiva[++len] = i;
        viz[i] = 1;
    }


    for(int i=n-1; i>=1; --i)
    {
        if(viz[i])  continue;
        while(plan(A[stiva[len-1]],A[stiva[len]],A[i]) <= 0)
            --len;
        stiva[++len] = i;
    }
}

void afisare()
{
    fout<<len-1<<"\n";
    for(int i=2; i<=len; ++i)
        fout<<fixed<<setprecision(12)<<A[stiva[i]].x<<" "<<A[stiva[i]].y<<"\n";
}

int main()
{
    citire();

    Graham();

    afisare();

    fin.close(); fout.close();
    return 0;
}