Cod sursa(job #2373206)

Utilizator alexilasiAlex Ilasi alexilasi Data 7 martie 2019 12:42:46
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

#define point pair <double, double>
#define x first
#define y second

using namespace std;


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

const int nMax = 120010;
const double EPS = 1e-12;

int n, i, h;
int st[nMax], vis[nMax];
point v[nMax];

bool check(point o, point a, point b)
{
    return ((a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y) < EPS);
}

int main()
{
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v+1, v+n+1);
    st[++h] = 1; st[++h] = 2;
    for(i=1; i<=n; i++)
    {
        if(vis[i] == true) continue;
        while(h >= 2 && check(v[st[h-1]], v[st[h]], v[i]))
            vis[st[h--]] = false;
        st[++h] = i;
        vis[i] = true;
    }
    for(i=n-1; i>0; i--)
    {
        if(vis[i] == true) continue;
        while(h >= 2 && check(v[st[h-1]], v[st[h]], v[i]))
            vis[st[h--]] = false;
        st[++h] = i;
        vis[i] = true;
    }
    fout << h-1 << '\n';
    for(i=1; i<h; i++)
        fout << v[st[i]].x << " " << v[st[i]].y << '\n';
    return 0;
}