Cod sursa(job #2869643)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 11 martie 2022 18:37:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>

#define NMAX 120005
#define EPS 1e-9

using namespace std;

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

typedef long double ld;

struct elem {
    ld x, y, val;
} a[NMAX], c;

int n, st[NMAX], ans;

inline ld vabs(const ld X) {
    return X > 0 ? X : - X;
}

inline bool isEqual(const ld A, const ld B) {
    return vabs(A - B) <= EPS;
}

inline ld dist(const elem A, const elem B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

inline ld crossProd(const elem A, const elem B, const elem C) {
    return A.x * B.y + C.x * A.y + B.x * C.y - C.x * B.y - A.x * C.y - B.x * A.y;
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);
    fin >> n;
    int primulPct = 1;
    for(int i = 1; i <= n; ++i) {
        fin >> a[i].x >> a[i].y;
        c.x += a[i].x, c.y += a[i].y;
        if(a[primulPct].y > a[i].y || (a[primulPct].y == a[i].y && a[primulPct].x > a[i].x)) primulPct = i;
    }
    c.x /= n, c.y /= n;
    swap(a[primulPct], a[1]);
    sort(a + 2, a + n + 1, [](const elem A, const elem B) {
        return crossProd(a[1], A, B) > 0;
    });
    st[1] = 1, st[2] = 2, ans = 2;
    for(int i = 3; i <= n; ++i) {
        while(ans >= 2 && crossProd(a[st[ans - 1]], a[st[ans]], a[i]) < 0)
            --ans;
        st[++ans] = i;
    }
    fout << ans << "\n";
    for(int i = 1; i <= ans; ++i)
        fout << fixed << setprecision(12) << a[st[i]].x << " " << a[st[i]].y << "\n";
    return 0;
}