Cod sursa(job #3358002)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 22:49:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct punct {
    long long x, y;
};

long long orientare(punct a, punct b, punct c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(punct a, punct b) {
    long long orient = orientare({0, 0}, a, b);
    if (orient != 0) return orient > 0;
    return (a.x * a.x + a.y * a.y) < (b.x * b.x + b.y * b.y);
}

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

    int n;
    fin >> n;

    vector<punct> v(n + 1);
    for (int i = 1; i <= n; i++) {
        fin >> v[i].x >> v[i].y;
    }

    sort(v.begin() + 1, v.end(), [](punct a, punct b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    vector<punct> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() >= 2 && orientare(st[st.size() - 2], st.back(), v[i]) <= 0) {
            st.pop_back();
        }
        st.push_back(v[i]);
    }

    for (int i = n - 1; i >= 1; i--) {
        while (st.size() >= 2 && orientare(st[st.size() - 2], st.back(), v[i]) <= 0) {
            st.pop_back();
        }
        st.push_back(v[i]);
    }

    st.pop_back();

    fout << st.size() << '\n';
    for (auto p : st) {
        fout << fixed;
        fout.precision(6);
        fout << p.x << ' ' << p.y << '\n';
    }

    return 0;
}