Cod sursa(job #3292552)

Utilizator adelinapetreAdelina Petre adelinapetre Data 8 aprilie 2025 15:30:12
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define double long double
using namespace std;

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

const int Nmax = 120005;

struct punct
{
    double x, y;
}p[Nmax];

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

int semn(punct a, punct b, punct c)//imi da semnul determinantului
{
    double det = a.x * b.y - b.y * c.x + b.x * c.y - c.y * a.x + c.x * a.y  - a.y * b.x;
    if (det > 0) return 1;
    if (det < 0) return -1;
    return 0;
}

int ans[Nmax];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;
    sort(p + 1, p + n + 1, cmp);
    ans[++ans[0]] = 1;
    ans[++ans[0]] = 2;
    for (int i = 3; i <= n; i++)
    {
        int sz = ans[0];
        while (sz > 1 && semn(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
        {
            ans[0]--;
            sz = ans[0];
        }
        ans[++ans[0]] = i;
    }
    for (int i = n - 1; i >= 1; i--)//n e ult punct pus
    {
        int sz = ans[0];
        while (sz > 1 && semn(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
        {
            ans[0]--;
            sz = ans[0];
        }
        ans[++ans[0]] = i;
    }
    cout << ans[0] - 1 << '\n';
    for (int i = 1; i < ans[0]; i++)//ult punct e acelasi cu primul
        cout << fixed << setprecision(12) << p[ans[i]].x << " " << p[ans[i]].y << '\n';
}