Cod sursa(job #3347916)

Utilizator EricMartinmartin petru eric EricMartin Data 18 martie 2026 21:34:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb

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

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

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

int valfinal[120001];
int main()
{
    int n;
    cin >>n;
    for (int i = 1; i <= n; i++)
    {
        cin >>v[i].y>>v[i].x;
        v[i].x += 1000000000;
        v[i].y += 1000000000;
    }
    int st = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i].x < v[st].x)
            st = i;
    }
    int cnt = 0;
    int p = st, q;
    while (cnt < n)
    {
        valfinal[cnt] = p;
        cnt++;
        if (p == n)
        {
            q = 1;
        }
        else
        {
            q = p + 1;
        }
        for (int i = 1; i <= n; i++)
        {
            // Calculam orientarea: (y2-y1)*(x3-x2) - (x2-x1)*(y3-y2)
            long double val = (v[q].y - v[p].y) * (v[i].x - v[q].x) - (v[q].x - v[p].x) * (v[i].y - v[q].y);
            if (val < 0)
                q = i;
        }
        p = q;
        if (p == st)
        {
            break;
        }
    }
    cnt--;
    cout <<cnt - 1<<"\n";
    for (int i = 1; i < cnt; i++)
    {
        cout <<fixed<<setprecision(6)<<v[valfinal[i]].y - 1000000000<<" ";
        cout <<fixed<<setprecision(6)<<v[valfinal[i]].x - 1000000000<<"\n";
    }

    return 0;
}