Cod sursa(job #1678369)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 7 aprilie 2016 11:34:14
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define mp make_pair
#define x first
#define y second
#define MAXN 120001
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,i,pos,head;
double a,b;
pair<double,double> v[MAXN],s[MAXN];
inline double cross_prod(pair<double,double>& a, pair<double,double>& b, pair<double,double>& c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp(pair<double,double>& a, pair<double,double>& b)
{
    return cross_prod(v[1],a,b)<0;
}
int main()
{
    f>>n;
    pos=1;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        v[i]=mp(a,b);
        if(v[i]<v[pos])pos=i;
    }
    swap(v[pos],v[1]);
    sort(v+2,v+n+1,comp);
    s[1]=v[1];
    s[2]=v[2];
    head=2;
    for(i=3;i<=n;i++)
    {
        while(head>=2&&cross_prod(s[head-1],s[head],v[i])>0)head--;
        s[++head]=v[i];
    }
    g<<head<<'\n';
    g<<fixed<<setprecision(9);
    for(i=head;i;i--)
        g<<s[i].x<<" "<<s[i].y<<'\n';
    f.close();
    g.close();
    return 0;
}