Cod sursa(job #1611588)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 24 februarie 2016 11:45:39
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;

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

#define N 120001
#define XY 1000000001

int n;
double X[N], Y[N];
int V[N];
int stiva[N], nstiva = 0;

double produs_vectorial(int a, int b, int c)
{
    return (X[b] - X[a]) * (Y[c] - Y[a]) - (Y[b] - Y[a]) * (X[c] - X[a]);
}

bool cmp(int v1, int v2)
{
    return produs_vectorial(V[1], v1, v2) < 0;
}

int main()
{
    in >> n;

    for(int i = 1; i <= n; i++)
    {
        in >> X[i] >> Y[i];
        V[i] = i;
    }

    int punct_initial = 1;
    for(int i = 2; i <= n; i++)
        if(X[V[i]] < X[V[punct_initial]])
            punct_initial = i;

    swap(V[1], V[punct_initial]);
    sort(V + 2, V + n + 1, cmp);

    stiva[++nstiva] = V[1];
    stiva[++nstiva] = V[2];
    for(int i = 3; i <= n; i++)
    {
        while(nstiva >= 2 && produs_vectorial(stiva[nstiva -  1], stiva[nstiva], V[i]) > 0)
            nstiva--;
        stiva[++nstiva] = V[i];
    }

    out << nstiva << '\n';
    for(int i = nstiva; i >= 1; i--)
        out << setprecision(12) << X[stiva[i]] << ' ' << Y[stiva[i]] << '\n';

    return 0;
}