Cod sursa(job #2971184)

Utilizator IanisBelu Ianis Ianis Data 26 ianuarie 2023 19:40:23
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif

#define endl '\n'

const int NMAX = 120005;

struct Point {
    double x, y;
    bool operator==(const Point &p) {
        return x == p.x && y == p.y;
    }
};

int n;
Point a[NMAX];
vector<int> st;

inline double det(const Point &a, const Point &b, const Point &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;
}

void read() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i].x >> a[i].y;
    }
}

int cmp(const Point &a, const Point &b) {
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

void solve() {
    st = {1, 2};
    for (int i = 3; i <= n; i++) {
        if (a[st.back()] == a[i]) continue;
        while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) < 0) {
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = n - 1; i >= 1; i--) {
        if (a[st.back()] == a[i]) continue;
        while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) < 0) {
            st.pop_back();
        }
        st.push_back(i);
    }

    fout << st.size() - 1 << endl;
    for (int i = 0; i < st.size() - 1; i++) {
        fout << setprecision(12) << fixed << a[st[i]].x << ' ' << a[st[i]].y << endl;
    }
}

int main() {
    read();
    sort(a + 1, a + n + 1, cmp);
    solve();
    return 0;
}