Cod sursa(job #2875394)

Utilizator 100pCiornei Stefan 100p Data 21 martie 2022 16:26:45
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define FILES freopen("infasuratoare.in","r",stdin);\
              freopen("infasuratoare.out","w",stdout);
#define add emplace_back
#define mp make_pair
#define fastio ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
using namespace std;
vector<pair<double,double>> v;
vector<pair<double,double>> Hull;
int n;
double a,b;
double cp(pair<double,double>a,pair<double,double> b,pair<double,double>c)
{
    a.first -= c.first, b.first -= c.first;
    a.second -= c.second, b.second -= c.second;
    return a.first * b.second - a.second * b.first;
}
void Solve()
{
    vector<pair<double,double>> pre;
    int sz = 0;
    for(int i = 0;i < v.size(); ++i)
    {
        if(pre.size() < 2)
        {
            sz++;
            pre.add(v[i]);
            continue;
        }

        while(pre.size() >= 2 && cp(pre[sz-1],v[i],pre[sz-2]) > 0.0)
            sz--,pre.pop_back();
        pre.add(v[i]);
        sz++;
        for(int j = 0;j < pre.size(); ++j)
            cout << pre[j].first << ' ' << pre[j].second << '\n';
        cout << '\n';
    }
    for(int i = 0;i < pre.size(); ++i) Hull.add(pre[i]);
}
int main()
{
    fastio
    FILES
    cin >> n;
    for(int i = 1;i <= n; ++i, cin >> a >> b, v.add(mp(a,b)));
    sort(v.begin(),v.end());
    Solve();
    reverse(v.begin(),v.end());
    Hull.pop_back();
    Solve();
    Hull.pop_back();
    cout << Hull.size() << '\n';
    for(int i = 0;i < Hull.size(); ++i, cout << Hull[i-1].first << ' ' << Hull[i-1].second << '\n');
}