Cod sursa(job #3293184)

Utilizator cattyAninisCatrinel catty Data 10 aprilie 2025 17:21:56
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct pr
{
    double a, b;
    bool operator< (const pr &x) const
    {
        return (make_pair (a, b) < make_pair (x.a, x.b));
    }
};
pr v[120005], rf;
double x, y;
int n, sz, poz;
vector<pr> ans;
pr operator - (pr a, pr b)
{
    return {a.a - b.a, a.b - b.b};
}
double unghi (pr a, pr b, pr rf)
{
    pr x1 = a - rf;
    pr x2 = b - rf;
    return x1.a * x2.b - x1.b * x2.a;
}
double lung (pr pct)
{
    return pct.a * pct.a + pct.b * pct.b;
}
bool cr (pr a, pr b)
{
    double ung = unghi (a, b, rf);
    if (ung == 0)
    {
        return lung (a - rf) < lung (b - rf);
    }
    return ung > 0;
}
int main()
{
    ios_base::sync_with_stdio (false);
    in.tie (0);
    out.tie (0);
    in >> n;
    for (int i = 1; i <= n; ++i)
    {
        in >> x >> y;
        v[i] = {x, y};
    }
    sort (v + 1, v + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while (sz > 1 && unghi (ans[sz - 2], v[i], ans.back()) > 0)
            ans.pop_back(), --sz;
        ans.push_back (v[i]);
        ++sz;
    }
    ans.pop_back();
    --sz;
    reverse (v + 1, v + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while (sz > 1 && unghi (ans[sz - 2], v[i], ans.back()) > 0)
            ans.pop_back(), --sz;
        ans.push_back (v[i]);
        ++sz;
    }
    ans.pop_back();
    --sz;
    out << sz << '\n';
    rf = {0, 0};
    sort (ans.begin(), ans.end(), cr);
    out << fixed << setprecision (12);
    for (auto i : ans)
        out << i.a << ' ' << i.b << '\n';
}