Cod sursa(job #3336866)

Utilizator Turcanu_DavidTurcanu David Turcanu_David Data 26 ianuarie 2026 13:10:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast", "unroll-loops")

using namespace std;

using ll = long long;
using ld = long double;
#define int ll
using pii = pair<int, int>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 67;
const int MAXN = 1e5 + 5;

int ox, oy;

struct point
{
    ld x, y;
};

vector<point> v;

ld det(point a, point b, point c)
{
    return (a.x * b.y - a.y * b.x) + (b.x * c.y - b.y * c.x) + (c.x * a.y - c.y * a.x);
}

vector<point> hull(vector<point> v)
{
    vector<point> up, dw;
    sort(v.begin(), v.end(), [&](point a, point b){
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });
    for(point p : v)
    {
        while(up.size() >= 2 && det(up[up.size() - 2], up[up.size() - 1], p) >= 0)
        {
            up.pop_back();
        }
        up.push_back(p);
    }
    for(point p : v)
    {
        while(dw.size() >= 2 && det(dw[dw.size() - 2], dw[dw.size() - 1], p) <= 0)
        {
            dw.pop_back();
        }
        dw.push_back(p);
    }
    dw.pop_back();
    reverse(up.begin(), up.end());
    up.pop_back();
    for(point p : up)
        dw.push_back(p);
    return dw;
}

ld dist(point a, point b)
{
    return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int32_t main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n;
    cin >> n;
    vector<point> v;
    for(int i = 1; i <= n; i++)
    {
        ld x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    if(n == 1)
    {
        for(auto [x, y] : v)
        {
            cout << fixed << setprecision(12) << x << ' ' << y << '\n';
        }
        return 0;
    }
    v = hull(v);
    cout << v.size() << '\n';
    for(auto [x, y] : v)
    {
        cout << fixed << setprecision(12) << x << ' ' << y << '\n';
    }
    return 0;
}