Cod sursa(job #2648555)

Utilizator MacaroaneFierteSimandan Paul MacaroaneFierte Data 11 septembrie 2020 14:24:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int nmax = 120005;

int n;
int st[nmax], vf;
struct pct 
{
    double x, y;
} x[nmax], stmin;

double panta(const pct& a, const pct& b)
{
    return (b.y-a.y)/(b.x-a.x);
}

bool cmp(const pct& x, const pct& y)
{
    return panta(stmin, x) < panta(stmin, y);
}

double det(const pct& a, const pct& b, const pct& c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> x[i].x >> x[i].y;
    
    stmin = x[1];
    int j = 1;
    for (int i = 2; i <= n; i++)
        if (x[i].x < stmin.x || (x[i].x == stmin.x && x[i].y < stmin.y))
        {
            stmin = x[i];
            j = i;
        }
    
    
    
    swap(x[1], x[j]);
    
    sort(x+2, x+n+1, cmp);
    
    vf = 2;
    st[1] = 1;
    st[2] = 2;
    
    for (int i = 3; i <= n; i++)
    {
        while (vf >= 2 && det(x[st[vf-1]], x[st[vf]], x[i]) <= 0)
            vf--;
        vf++;
        st[vf] = i;            
    }
    
    g << vf << '\n';
    for (int i = 1; i <= vf; i++)
    {
        g << fixed << setprecision(6) << x[st[i]].x << ' ' << x[st[i]].y << '\n';
    }
    
    return 0;
}