Cod sursa(job #1399359)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 24 martie 2015 18:28:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
const int NMAX=120004;
int n, i;
typedef pair<double, double> punct;
punct v[NMAX], st[NMAX];
inline double panta(const punct &a,const punct &b,const punct &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline int cmp(const punct& a, const punct& b)
{
    return panta(v[1], a, b)<0;
}
void sortare()
{
    int i, p=1;
    for (i=2; i<=n; ++i)
        if (v[i]<v[p])
            p=i;
    swap(v[1],v[p]);
    sort(v+2,v+n+1,cmp);
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i].x>>v[i].y;
    sortare();
    st[1]=v[1];
    st[2]=v[2];
    int vf=2;
    for(i=3; i<=n; i++)
    {
        while(vf>=2&&panta(st[vf-1],st[vf],v[i])>0)
            vf--;
        st[++vf]=v[i];
    }
    cout<<vf<<'\n';
    for(i=vf; i>=1; i--)
        cout<<setprecision(8)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}