Cod sursa(job #3373826)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 7 noiembrie 2026 22:40:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define ff first
#define ss second
#define vpi vector<pii>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORR(i, a, b) for(int i = (a); i >= (b); --i)
#define pb push_back
using namespace std;
const int N = 1e6 + 9;
const bool testcases = false;

const string INPUT_FILE = "infasuratoare";
ifstream fin(INPUT_FILE + ".in");
ofstream fout(INPUT_FILE + ".out");
#define cin fin
#define cout fout

int n;
using pd = pair<double, double>;
#define x first
#define y second
pd a[N];

pd operator - (pd const& a, pd const& b) {
    return {a.x - b.x, a.y - b.y};
}

double cross(pd const& a, pd const& b) {
    return a.x * b.y - a.y * b.x;
}

void solve_testcase() {
    cin >> n;

    {
        FOR(i, 1, n) {
            cin >> a[i].ff >> a[i].ss;
        }
    }

    int p = 1;
    FOR(i, 2, n) {
        if (a[i].ff < a[p].ff || (a[i].ff == a[p].ff && a[i].ss < a[p].ss)) {
            p = i;
        }
    }

    swap(a[1], a[p]);
    sort(a + 2, a + n + 1, [&](auto const& x, auto const& y) {
        return cross(x - a[1], y - a[1]) < 0;
    });

    vector<pd> v;
    FOR(i, 1, n) {
        while (v.size() > 1 && cross(v[v.size() - 1] - a[i], v[v.size() - 2] - a[i]) <= 0) {
            v.pop_back();
        }
        v.pb(a[i]);
    }

    reverse(v.begin(), v.end());
    cout << v.size() << '\n';
    cout << fixed << setprecision(12);
    for (auto e : v) {
        cout << e.x << ' ' << e.y << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    if (testcases) cin >> t;
    while (t --) solve_testcase();
    return 0;
}