Cod sursa(job #2046994)

Utilizator BourucLiviuBouruc Petru Liviu BourucLiviu Data 24 octombrie 2017 13:43:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define N 120005

using namespace std;

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

struct punct
{
    double x, y;
} v[N];

int n, st[N], top;
bool viz[N];

double F(int i, int j, int p)
{
    return v[p].x*(v[i].y - v[j].y) + v[p].y*(v[j].x - v[i].x) + v[i].x*v[j].y - v[i].y*v[j].x;
}

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

void Hill()
{
    sort(v+1, v+n+1, cmp);
    st[1] = 1; st[2] = 2; 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; --i)
        if(!viz[i])
        {
            while(F(st[top-1], st[top], i) < 0)
            {
                viz[st[top]] = 0;
                top--;
            }
            st[++top] = i;
        }
}

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

    Hill();

    fout << top-1 << '\n';
    for(int i = 2; i <= top; ++i)
        fout << setprecision(12) << fixed << v[st[i]].x << " " << v[st[i]].y << '\n';
    return 0;
}