Cod sursa(job #2878542)

Utilizator alextmAlexandru Toma alextm Data 27 martie 2022 10:22:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
 
#define x first
#define y second
#define Point pair<double, double>
 
double det(Point a, Point b, Point c) { // unghiul polar
    return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}
 
int main() {
    int n; 
    fin >> n;
    vector<Point> pts(n);
    for (int i = 0; i < n; i++)
        fin >> pts[i].x >> pts[i].y;
 
    swap(pts.front(), *min_element(pts.begin(), pts.end())); // functie pt determinarea minimului
   
    
    sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) { // sortare cu functie inline
        return det(a, pts[0], b) < 0;
    });
 
    vector<Point> st; // Adaugam punctele in infasuratoare
    st.push_back(pts[0]);
    st.push_back(pts[1]);
    for (int i = 2; i < n; i++) {
        while (st.size() > 2 && det(st[st.size() - 2], st[st.size() - 1], pts[i]) < 0)
            st.pop_back();
        st.push_back(pts[i]);
    }
 
    fout << st.size() << fixed << setprecision(6) << '\n';
    for (int i = st.size() - 1; i >= 0; i--)
        fout << st[i].x << ' ' << st[i].y << '\n';
 
    return 0;
}