Cod sursa(job #3310399)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 13 septembrie 2025 16:23:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <iomanip>

using namespace std;
const int NMAX = 120000; ///120000 pt infasuratoare
using ld = long double;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

double p0x, p0y;
struct puncte{
    double x, y;
    double unghi;
    bool operator <(const puncte& rhs) const {
        if(unghi != rhs.unghi)
            return unghi < rhs.unghi;
        double dista = (p0x - x) * (p0x - x) + (p0y - y) * (p0y - y);
        double distb = (p0x - rhs.x) * (p0x - rhs.x) + (p0y - rhs.y) * (p0y - rhs.y);
        return dista < distb;
    }
}v[NMAX + 2];
set <puncte> s;

double determ(const puncte& a, const puncte& b, const puncte& c) {
    return a.x * b.y + b.x * c.y + c.x * a.y -
           a.y * b.x - b.y * c.x - c.y * a.x;
}

vector <puncte> st;
int main() {
    int n, m;
    cin >> n;
    p0x = 0, p0y = 0;
    for(int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        p0x += v[i].x, p0y += v[i].y;
    }
    p0x /= n, p0y /= n;
    for(int i = 1; i <= n; i++)
        v[i].unghi = atan2(v[i].y - p0y, v[i].x - p0x);
    sort(v + 1, v + n + 1);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i = 3; i <= n; i++) {
        while(st.size() >= 2 && determ(st[st.size() - 2], st[st.size() - 1], v[i]) < 0)
            st.pop_back();
        st.push_back(v[i]);
    }
    int sizee = st.size(), ult = 0; /// o sa se tot schimbe size-ul
    while(sizee > 3) { ///ne intereseaza doar cum se termina CAPETELE
        if(determ(st[st.size() - 2], st[st.size() - 1], st[ult]) < 0) {
            st.pop_back();
            sizee--;
        }
        else if(determ(st[st.size() - 1], st[ult], st[ult + 1]) < 0) {
            ult++;
            sizee--;
        }
        else
            break;
    }
    cout << sizee << '\n';
    for(int i = ult; i < st.size(); i++)
        cout << setprecision(12) << fixed << st[i].x << " " << st[i].y << '\n';
    return 0;
}