Cod sursa(job #3317211)

Utilizator IuriIamandi Iuri Iuri Data 22 octombrie 2025 18:42:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int dim = 120002;
struct coord{
    double x, y;
    int cod;
} v[dim];
int st[dim];
bool cmp(coord A, coord B){
    if(A.x != B.x)
        return A.x < B.x;
    else
        return A.y < B.y;
}
double arie(coord a, coord b, coord 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 main()
{
    int n, i, k = 1, ck;
    in >> n;
    for(i = 1; i <= n; ++i)
        in >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    coord a = v[1], b = v[n];
    for(i = 2; i <= n - 1; ++i)
        if(arie(a, b, v[i]) < 0)
            v[i].cod = 1;
        else
            v[i].cod = 2;
    st[k] = 1;
    for(i = 2; i <= n; ++i)
        if(v[i].cod <= 1){
            while(k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                --k;
            st[++k] = i;
        }
    ck = k;
    st[k] = n;
    for(i = n - 1; i; --i)
        if(v[i].cod == 2 || v[i].cod == 0){
            while(k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                --k;
            st[++k] = i;
        }
    --k;
    out << k << '\n';
    for(i = 1; i <= k; ++i)
        out << fixed << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
    return 0;
}