Cod sursa(job #3316720)

Utilizator EricMartinmartin petru eric EricMartin Data 20 octombrie 2025 12:25:42
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb

#include <fstream>
#include <algorithm>
using namespace std;

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

struct a
{
    double x,y;
    int loc;
}v[120001];

int cmp(a A , a B)
{
    return A.x < B.x;
}

int linie (a A , a B , a C)
{
    return  A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}

int st[120001];
int main()
{
    int n;
    cin >>n;
    for (int i = 1; i <= n; i++)
    {
        cin >>v[i].x>>v[i].y;
    }
    sort (v + 1 , v + n + 1 , cmp);
    for (int i = 2; i < n; i++)
    {
        ///loc = 1 ==> sub sau loc = 2 ==> peste
        if (linie(v[1] , v[i] , v[n]) < 0)
        {
            v[i].loc = 1;
        }
        else
        {
            v[i].loc = 2;
        }
    }
    st[1] = 1;
    int k = 1;
    for (int i = 2; i <= n; i++)
    {
        if (v[i].loc == 1 || v[i].loc == 0)
        {
            while (k > 1 && linie(v[st[k - 1]], v[st[k]] , v[i]) > 0)
            {
                k--;
            }
            k++;
            st[k] = i;
        }
    }
    int c = k;
    st[k] = n;
    for (int i = n - 1; i >= 1; i--)
    {
        if (v[i].loc == 2 || v[i].loc == 0)
        {
            while (k > c && linie(v[st[k - 1]] , v[st[k]] , v[i]) > 0)
            {
                k--;
            }
            k++;
            st[k] = i;
        }
    }
    cout <<k - 1<<"\n";
    for (int i = k - 1; i >= 1; i--)
    {
        cout <<v[st[i]].x<<".000000 "<<v[st[i]].y<<".000000\n";
    }
    return 0;
}