Cod sursa(job #3336864)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 26 ianuarie 2026 13:04:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;
const int NMAX = 120000;
const int INF = 21e8;
using ll = long double;

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

struct puncte{
    ll x, y;
}init[NMAX + 2], p0 = {INF, INF};

ll dist(const puncte& a, const puncte& b) { ///fara radical
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

ll determ(const puncte& a, const puncte& b, const puncte& c) { ///NU am impartit la 2
    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);
}

bool cmp(const puncte& a, const puncte& b) {
    ll panta1 = (a.y - p0.y) * (b.x - p0.x);
    ll panta2 = (b.y - p0.y) * (a.x - p0.x);
    if(panta1 != panta2)
        return panta1 < panta2;
    return dist(p0, a) < dist(p0, b);
}
vector <puncte> v; ///stack-ul adica
int main() {
    int n, id = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> init[i].x >> init[i].y;
        if(init[i].x < p0.x || (init[i].x == p0.x && init[i].y < p0.y)) {
            p0 = init[i];
            id = i;
        }
    }
    // cout << "ayoo " << p0.x << " " << p0.y << '\n';
    /*if(n == 1) {
        cout << 0;
        return 0;
    }
    if(n == 2) {
        cout << sqrt(dist(init[1], init[2]));
        return 0;
    }*/
    if(id != 1)
        swap(init[1], init[id]);
    sort(init + 2, init + n + 1, cmp);
    /*for(int i = 1; i <= n; i++)
        cout << init[i].x << " " << init[i].y << '\n';
    cout << '\n';*/
    v.push_back(init[1]);
    v.push_back(init[2]);
    for(int i = 3; i <= n; i++) {
        while(v.size() >= 2 && determ(v[v.size() - 2], v.back(), init[i]) < 0)
            v.pop_back();
        v.push_back(init[i]);
    }

    cout << v.size() << '\n';
    for(auto p : v)
        cout << setprecision(12) << fixed << p.x << " " << p.y << '\n';
    return 0;
}