Cod sursa(job #2875408)

Utilizator 100pCiornei Stefan 100p Data 21 martie 2022 16:46:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 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>> Uh,Dh;
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;
}
vector<pair<double,double>> 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++;
    }
    return pre;
}
bool cmp(pair<double,double> a,pair<double,double> b)
{
    return cp(a,b,{0.0,0.0}) >= 0;
}
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());
    Uh = Solve();
    reverse(v.begin(),v.end());
    Dh = Solve();
    reverse(Uh.begin(),Uh.end());
    reverse(Dh.begin(),Dh.end());
    Uh.pop_back();
    Dh.pop_back();
    cout << Uh.size()+Dh.size() << '\n';
    for(int i = 0;i < Dh.size(); ++i, cout << setprecision(12) << fixed << Dh[i-1].first << ' ' << Dh[i-1].second << '\n');
    for(int i = 0;i < Uh.size(); ++i, cout << setprecision(12) << fixed << Uh[i-1].first << ' ' << Uh[i-1].second << '\n');

}