Cod sursa(job #3226365)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 21 aprilie 2024 11:21:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const int max_size = 12e4 + 20;

pair <double, double> v[max_size];
vector <int> sus, jos;

double arie (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

void solve ()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; i++)
    {
        while (sus.size() > 1 && arie(v[sus[sus.size() - 2]], v[sus.back()], v[i]) >= 0)
        {
            sus.pop_back();
        }
        while (jos.size() > 1 && arie(v[jos[jos.size() - 2]], v[jos.back()], v[i]) <= 0)
        {
            jos.pop_back();
        }
        sus.push_back(i);
        jos.push_back(i);
    }
    vector <pair <double, double>> ans;
    for (auto f : jos)
    {
        ans.push_back(v[f]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    for (auto f : sus)
    {
        ans.push_back(v[f]);
    }
    cout << ans.size() << '\n';
    for (auto f : ans)
    {
        cout << fixed << setprecision(6) << f.first << " " << f.second << '\n';
    }
    cout << '\n';
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    //cin >> tt;
    tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}