Cod sursa(job #2829932)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 9 ianuarie 2022 11:32:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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



struct point {
    long double x, y;
};

point points[10003];

int N, k;

int st[10003];
bool sel[10003];


long long det(point a, point b, point c)
{
    // a11 a12 a13
    // a21 a22 a23
    // a31 a32 a33

    return a.x*b.y*1+a.y*1*c.x+1*b.x*c.y-1*b.y*c.x-1*c.y*a.x-1*a.y*b.x;
}


void infasuratoare()
{
    st[++k] = 1;
    st[++k] = 2;

    sel[1] = sel[2] = true;

    // prima bucata
    for(int i = 3; i <= N; i++)
    {
        while(k >= 2 && det(points[st[k - 1]], points[st[k]], points[i]) >= 0)
        {
            sel[st[k]] = 0;
            --k;
        }
        st[++k] = i;
        sel[i] = true;
    }

    for(int i = N; i >= 1; i--)
    {
        if(sel[i])
            continue;

        while(k >= 2 && det(points[st[k - 1]], points[st[k]], points[i]) >= 0)
        {
            sel[st[k]] = 0;
            --k;
        }
        st[++k] = i;
        sel[i] = true;
    }

}
int main()
{
    f >> N;
    for(int i = 1; i <= N; i++)
    {
        f >> points[i].x >> points[i].y;
    }

    sort(points + 1, points + N + 1, [](point a, point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    infasuratoare();

    g << k - 1 << "\n";

    for(int i = k - 1; i >= 1; i--)
        g << setprecision(6) << fixed << points[st[i]].x << " " << points[st[i]].y << "\n";
    return 0;
}