Cod sursa(job #2869581)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 11 martie 2022 17:41:23
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 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;
} 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;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].x >> a[i].y,
        c.x += a[i].x, c.y += a[i].y;
    c.x /= n, c.y /= n;
    sort(a + 1, a + n + 1, [](const elem A, const elem B) {
         const ld crtA = atan2(A.y - c.y, A.x - c.x),
                  crtB = atan2(B.y - c.y, B.x - c.x);
        if(isEqual(crtA, crtB)) return dist(A, c) > dist(B, c);
        return crtA < crtB;
    });
    a[++n] = a[1];
    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;
    }
    --ans;
    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;
}