Cod sursa(job #2047776)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 25 octombrie 2017 11:33:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

int nr, i, k;

struct nod
{
    double x, y;
}v[122005],st[122005];

bool cr1(nod a, nod b)
{
    if(a.x != b.x)
    return a.x < b.x;
    return a.y < b.y;
}

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

bool cr2(nod a, nod b)
{
    return det(v[1], a, b) < 0;
}

int main()
{
    cin >> nr;
    for(i=1; i <= nr; i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort(v+1, v+nr+1, cr1);
    sort(v+2, v+nr+1, cr2);
    st[1] = v[1];
    st[2] = v[2];
    st[3] = v[3];
    k = 3;

    for(i=4; i <= nr; i++)
    {
        while((k >= 3) && (det(st[k-1], st[k], v[i]) > 0))
            k--;
        k++;
        st[k] = v[i];
    }
    cout << k << '\n';
    cout<<fixed<<setprecision(12);
    for(i=k; i > 0; i--)
    {
        cout << st[i].x << ' ' << st[i].y << '\n';
    }
}