Cod sursa(job #3339005)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 5 februarie 2026 17:49:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

typedef pair <long double, long double> punct;

const int nmax = 12e4 + 5;

int n;
punct v[nmax];

double det3 (punct a, punct b, punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp (punct x, punct y)
{
    return det3 (v[1],x,y) < 0;
}

int k = 2, st[nmax];

void convexhull ()
{
    int poz = 1;
    for (int i = 2; i <= n; i++)
    {
        if (v[i] < v[poz])
            poz = i;
    }
    swap (v[1], v[poz]);
    sort (v + 2, v + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        while (k >= 2 && det3 (v[st[k - 1]], v[st[k]], v[i]) > 0)
            k--;
        st[++k] = i;
    }
    reverse (st + 1, st + k + 1);
}

int main ()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    convexhull ();
    fout << k << '\n';
    for (int i = 1; i <= k; i++)
        fout << fixed << setprecision (12) << v[st[i]].x << " " << v[st[i]].y << '\n';
}