Cod sursa(job #3317155)

Utilizator mateilupuMatei Lupu mateilupu Data 22 octombrie 2025 16:30:07
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

int st[120001];

struct ura {
    double x, y;
    int ok;
};

ura v[120001];

bool cmp(ura a, ura b) {
    if(a.x < b.x)
        return true;
    if(a.x == b.x && a.y < b.y)
        return true;
    return false;
}

double arie(ura a, ura b, ura c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}

int main()
{
    ifstream cin ("infasuratoare.in");
    ofstream cout ("infasuratoare.out");
    int n, i, k, kc;
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    for(i = 2; i < n; i++) {
        if(arie(v[1], v[n], v[i]) < 0)
            v[i].ok = 1;
        else
            v[i].ok = 2;
    }
    st[1] = 1;
    k = 1;
    for(i = 2; i < n; i++) {
        if(v[i].ok == 1) {
            for(; k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
            }
            k++;
            st[k] = i;
        }
    }
    k++;
    st[k] = n;
    kc = k;
    for(i = n - 1; i > 1; i--) {
        if(v[i].ok == 2) {
            for(; k > kc && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
            }
            k++;
            st[k] = i;
        }
    }
    cout << k << '\n';
    for(i = 1; i <= k; i++) {
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
    }
    return 0;
}