Cod sursa(job #3200083)

Utilizator pifaDumitru Andrei Denis pifa Data 3 februarie 2024 14:39:26
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

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

using ll = long long;
struct pll
{
    double x, y;
};
const double eps = 1e-6;
ll det(pll a, pll b, pll c)
{
    double d = (a.x*b.y + b.x*c.y + c.x*a.y) - (b.y*c.x + c.y*a.x + a.y*b.x);
    if(d == 0)
        return 0;
    if(d > 0)
        return 1;
    return -1;
}
const int NMAX = 120005;
pll v[NMAX];
ll n;
vector<int> lower, upper, hull;
void compute()
{
    ll i;
    lower.pb(1);
    for(i = 2; i <= n; i++)
    {
        while(lower.size() >= 2 && det(v[lower[lower.size()-2]], v[lower[lower.size()-1]], v[i]) == -1)
            lower.pop_back();
        lower.pb(i);
    }
    upper.pb(1);
    for(i = 2; i <= n; i++)
    {
        while(upper.size() >= 2 && det(v[upper[upper.size()-2]], v[upper[upper.size()-1]], v[i]) == 1)
            upper.pop_back();
        upper.pb(i);
    }
    upper.pop_back();
    reverse(upper.begin(), upper.end());
    for(i = 0; i < lower.size(); i++)
        hull.pb(lower[i]);
    for(i = 0; i < upper.size(); i++)
        hull.pb(upper[i]);
}

signed main()
{
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    compute();
    out << hull.size() - 1 << '\n';
    for(int i = 0; i < hull.size() - 1; i++)
    {
        out << fixed << setprecision(6) << v[hull[i]].x << ' ';
        out << fixed << setprecision(6) << v[hull[i]].y;
        out << '\n';
    }
    return 0;
}