Cod sursa(job #2314275)

Utilizator tiberiu392Tiberiu Ungurianu tiberiu392 Data 8 ianuarie 2019 11:36:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <bits/stdc++.h>
#define Nmax 150005
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

double vrg = 1e-12;
bool vis[Nmax];
int n, i;
int st[Nmax], top=2;

struct db{
double x, y;
}v[Nmax], X;


double pr(db a, db b, db c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(db a, db b)
{
    if ( a.x == b.x ) return a.y < b.y ;
    return a.x < b.x ;
}

int main()
{
    f >> n;
    for ( i = 1 ; i <= n ; i++ )
    {
        f >> X.x >> X.y ;
        v[i] = X;
    }
    sort( v+1, v+n+1, cmp);

    st[1] = 1, st[2] = 2;
    vis[2] = 1;

    for ( i = 3 ; i <= n ; i++)
    {
        if( vis[i] == 1) continue;
        while ( top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < vrg )
        {
            vis[st[top]] = 0;
            top--;
        }
        st[++top] = i;
        vis[i] = i;
    }
    for ( i = n-1 ; i >= 1 ; i--)
    {
        if( vis[i] == 1) continue;
        while ( top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < vrg )
        {
            vis[st[top]] = 0;
            top--;
        }
        st[++top]=i;
        vis[i] = 1;
    }
   g << top-1 << '\n' << setprecision(12) << fixed;
    for (int i = top-1; i >= 1; i--)
        g << v[st[i]].x << " " << v[st[i]].y << '\n';


    return 0;
}