Cod sursa(job #3293181)

Utilizator cattyAninisCatrinel catty Data 10 aprilie 2025 16:14:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
#define pr pair<double,double>
#define a first
#define b second
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
pr v[120005], rf;
double x, y;
int n, sz;
double xm = -1e9, ym = -1e9;
int 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 punct)
{
    return punct.a * punct.a + punct.b * punct.b;
}
bool cr (pr a, pr b)
{
    double x = unghi (a, b, rf);
    if (x == 0)
    {
        return lung (a - rf) < lung (b - rf);
    }
    return x < 0;
}
bool cr1 (pr a, pr b)
{
    double x = unghi (a, b, rf);
    if (x == 0)
    {
        return lung (a - rf) < lung (b - rf);
    }
    return x > 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;
        if (x > xm)
            xm = x, ym = y, poz = i;
        else if (x == xm && y < ym)
            ym = y, poz = i;
        v[i] = {x, y};
    }
    rf = v[poz];
    sort (v + 1, v + n + 1, cr);
    ans.push_back (rf);
    sz = 1;
    for (int i = 2; 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;
    }
    out << sz << '\n';
    rf = {0, 0};
    sort (ans.begin(), ans.end(), cr1);
    out << fixed << setprecision (12);
    for (auto i : ans)
        out << i.a << ' ' << i.b << '\n';
}