Cod sursa(job #2044398)

Utilizator BourucLiviuBouruc Petru Liviu BourucLiviu Data 21 octombrie 2017 09:50:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define nmax 120005

using namespace std;

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

struct punct
{
    double x, y;
} a[nmax];

int n;
int st[nmax], top;
bool viz[nmax]; /// v[i] =1 daca este pe stiva

/// returneaza < 0 daca pct a[p] este in semiplanul - al dreptei det. de pct (a[i],a[j])
/// + daca e in semiplanul +
/// a[i] = A; a[j] = B
double F(int i, int j, int p)
{
    return a[p].x*(a[i].y-a[j].y) + a[p].y*(a[j].x-a[i].x) + a[i].x*a[j].y - a[j].x*a[i].y;

    /*a[1].x = a[1].y = 0; /// originea
    a[2].x = a[2].y = 6; /// bisectoare
    a[3].x = 7; a[3].y = 7;
    cout << F(1,2,3);*/
}

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

/// algoritmul lui Hill
void Hill()
{
    sort(a+1, a+n+1, cmp);
    st[++top] = 1;
    st[++top] = 2;
    viz[2] = 1;
    for(int i = 3; i <= n; ++i)
    {
        while(top > 1 && F(st[top-1], st[top], i) < 0)
        {
            viz[st[top]] = 0;
            top--;
        }
        st[++top] = i;
        viz[i] = 1;
    }

    for(int i = n-1; i >= 1; --i)
        if(viz[i] == 0)
        {
            while(F(st[top-1], st[top], i) < 0)
            {
                viz[st[top]] = 0;
                top--;
            }
            st[++top] = i;
            viz[i] = 1;
        }

}

void afisare()
{
    fout << top-1 << '\n';
    for(int i = 1; i < top; ++i)
        fout << setprecision(12) << fixed << a[st[i]].x << " " << a[st[i]].y << '\n';
    fout.close();
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].x >> a[i].y;
    fin.close();

    Hill();

    afisare();
    return 0;
}