Cod sursa(job #2674102)

Utilizator Iulia14iulia slanina Iulia14 Data 18 noiembrie 2020 16:46:31
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura{
    double x, y;
};
ura v[120005];
bool cmp(ura a, ura b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}
bool calc(ura a, ura b, ura c)
{
    return (c.y - a.y) * (b.x - a.x) <= (b.y - a.y) * (c.x - a.x);
}
int st[240005];
int viz[120005];
int main()
{
    int n, i, k, pas;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;
    sort (v + 1, v + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    k = 2;
    viz[2] = 1;
    pas = 1;
    i = 3;
    while (!viz[1])
    {
        if (!viz[i])
        {
            while (k > 1 && calc(v[st[k - 1]], v[st[k]], v[i]))
                viz[st[k--]] = 0;
            st[++k] = i;
            viz[i] = 1;
        }
        if (i == n)
            pas = -1;
        i += pas;
    }
    k--;
    cout << k;
    i = 1;
    while (i <= k)
    {
        cout << fixed << setprecision(12) << '\n' << v[st[i]].x << " " << v[st[i]].y;
        i++;
    }
    return 0;
}