Cod sursa(job #892182)

Utilizator bulbulicaAlexandrescu Cristian bulbulica Data 25 februarie 2013 22:46:47
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#define inf 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct
{
    double x,y,u;
}v[120006];
int n,i,ind[120006],st[120006],k,stp;
double xjos=inf,yjos=inf;
double unghi(pct a)
{
    double x=a.x-xjos,y=a.y-yjos;
    return (double)atan(y/x);
}
bool cmp(int i,int j)
{
    return v[i].u<v[j].u;
}
bool semn(pct a,pct b,pct c)
{
    return (a.x-b.x)*(b.y-c.y)<=(a.y-b.y)*(b.x-c.x);
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        ind[i]=i;
        if( v[i].x<xjos || (v[i].x==xjos && v[i].y<yjos) )
        {
            xjos=v[i].x;
            yjos=v[i].y;
            stp=i;
        }
    }
    v[stp].u=-inf;
    for(i=1;i<=n;i++)
        if(i!=stp)
            v[i].u=unghi(v[i]);
    sort(ind+1,ind+n+1,cmp);
    k=3;
    i=4;
    st[1]=stp;
    st[2]=ind[2];
    st[3]=ind[3];
    while(i<=n)
    {
        while( semn(v[st[k-1]],v[st[k]],v[ind[i]]) )
            k--;
        st[++k]=ind[i++];
    }
    g<<k<<'\n';
    g.precision(6);
    g.setf( ios::fixed, ios::floatfield );
    for(i=1;i<=k;i++)
        g<<(float)v[st[i]].x<<' '<<(float)v[st[i]].y<<'\n';
    return 0;
}