Cod sursa(job #1006414)

Utilizator shagarthAladin shagarth Data 6 octombrie 2013 22:59:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define MAX 120100
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,s[MAX],k;
bool viz[MAX];
struct vct
{
    double x,y;

}v[MAX];
long double cmp(vct A,vct B)
{
    if(A.x!=B.x)
        return A.x>B.x;
    else
        return A.y<B.y;
}
long double verf(int i,int j,int k)
{
    double vff;
    vff=v[i].x*v[j].y+v[j].x*v[k].y+v[i].y*v[k].x-v[i].y*v[j].x-v[j].y*v[k].x-v[i].x*v[k].y;
    return vff;
}
int main ()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,cmp);
    viz[2]=1;
    s[1]=1;
    s[2]=2;
    k=2;

    for(i=3;i<=n;++i)
    {
        if(verf(s[k-1],s[k],i)<0)
        {
            s[++k]=i;
            viz[i]=1;
        }
        else
        {
            while(verf(s[k-1],s[k],i)>=0 && k>1)
            {
                viz[s[k]]=0;
                s[k]=0;
                k--;
            }
            s[++k]=i;
            viz[i]=1;
        }
    }

    for(i=n-1;i>=1;--i)
    {
        if(!viz[i])
        {

            if(verf(s[k-1],s[k],i)<0)
            {
                s[++k]=i;
                viz[i]=1;
            }
            else
            {
                while(verf(s[k-1],s[k],i)>=0 && k>1)
                {
                    viz[s[k]]=0;
                    s[k]=0;
                    k--;
                }
                s[++k]=i;
                viz[i]=1;
            }
        }
    }
    g<<k-1<<"\n";
    k--;
    for(i=k-1;i>=1;--i)
        g<<fixed<<setprecision(6)<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
    g<<v[s[k]].x<<" "<<v[s[k]].y<<"\n";

    f.close();
    g.close();
    return 0;
}