Cod sursa(job #2388606)

Utilizator onipreponiprep oniprep Data 26 martie 2019 11:22:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

typedef pair<double,double> Pair;
const int N = 120010;
const double err = 1e-12;
int n,i,h;
int sk[N],prez[N];
Pair v[N];
bool check(Pair o, Pair a, Pair b)
{
    return ((a.first - o.first) * (b.second - o.second) - (b.first - o.first) * (a.second - o.second) < err);
}

int main()
{
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> v[i].first >> v[i].second;
    sort(v+1, v+n+1);
    sk[++h] = 1; sk[++h] = 2;
    prez[2] = true;
    for(i=1; i<=n; i++)
    {
        if(prez[i] == true) continue;
        while(h >= 2 && check(v[sk[h-1]], v[sk[h]], v[i]))
            prez[sk[h--]] = false;
        sk[++h] = i;
        prez[i] = true;
    }
    for(i=n-1; i>0; i--)
    {
        if(prez[i] == true) continue;
        while(h >= 2 && check(v[sk[h-1]], v[sk[h]], v[i]))
            prez[sk[h--]] = false;
        sk[++h] = i;
        prez[i] = true;
    }
    fout << h-1 << '\n';
    fout << setprecision(6) << fixed;
    for(i=1; i<h; i++)
        fout << v[sk[i]].first << " " << v[sk[i]].second << '\n';
    return 0;
}