Cod sursa(job #1175817)

Utilizator gapdanPopescu George gapdan Data 24 aprilie 2014 22:37:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
int i,k,n;
struct coord
{
    double x,y;
} v[120005],st[120005];
inline double panta(coord a,coord b,coord c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
inline bool cmp(coord r,coord q)
{
    return panta(v[1],r,q)<0;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    for (i=1;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
    }
    int pos=1;
    for (int i=2;i<=n;++i)
        if (v[i].y<v[pos].y) pos=i;
            else if (v[i].y==v[pos].y && v[i].x<v[pos].x) pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
    st[1]=v[1];
    st[2]=v[2];
    k=2;
    for (i=3;i<=n;++i)
    {
        while(k>=2 && panta(st[k-1],st[k],v[i])>0) --k;
        st[++k]=v[i];
    }
    g<<k<<'\n';
    for (i=k;i>=1;--i) g<<setprecision(9)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}