Cod sursa(job #3149721)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 11 septembrie 2023 16:21:19
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
const int NMAX=120005;

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

typedef long double ld;
typedef pair<ld, ld> pii;

ld det(pii, pii, pii);
vector <pii> convex_hull(pii [], int);
bool cmp(pii, pii);

pii v[NMAX], st[NMAX];
vector <pii> ans;
int n;

int main()
{
    int i;
    fin>>n;
    for(i=1; i<=n; i++) fin>>v[i].first>>v[i].second;
    ans=convex_hull(v, n);
    fout<<ans.size()<<'\n';
    for(auto i:ans) fout<<fixed<<setprecision(10)<<i.first<<' '<<i.second<<'\n';
    return 0;
}

vector <pii> convex_hull(pii v[], int n)
{
    int i, poz=0, cnt=0;
    pii pct={1e9, 1e9};
    for(i=1; i<=n; i++)
    {
        if(v[i].second<pct.second)
        {
            pct=v[i];
            poz=i;
        }
        else if(v[i].first<pct.first)
        {
            pct=v[i];
            poz=i;
        }
    }
    swap(v[1], v[poz]);
    sort(v+2, v+n+1, cmp);
    st[++cnt]=v[1];
    st[++cnt]=v[2];
    for(i=3; i<=n; i++)
    {
        while(cnt>1 && det(v[i], st[cnt-1], st[cnt])>0) cnt--;
        st[++cnt]=v[i];
    }
    vector <pii> ans;
    ans.clear();
    for(i=cnt; i>=1; i--) ans.push_back(st[i]);
    return ans;
}

bool cmp(pii a, pii b)
{
    return det(b, v[1], a)<0;
}

ld det(pii a, pii b, pii c)
{
    return b.first*c.second-b.second*c.first+a.first*(b.second-c.second)-a.second*(b.first-c.first);
}