Cod sursa(job #1142284)

Utilizator span7aRazvan span7a Data 13 martie 2014 18:01:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define M 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct coord
{
    long double x,y,tg;
};
coord L[120001];
int sol[120001],n,sf;
long double minx=M,miny=M;
int cmp(coord a,coord b)
{
    return a.tg>b.tg;
}
void muta(long double &x,long double &y)
{
    x=x-minx;
    y=y-miny;
}
void citire()
{
    int i,poz;
    long double x,y;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        L[i].x=x;L[i].y=y;
        if(minx>x)
            {
                minx=x;
                miny=y;
                poz=i;
            }
        else
            if(minx==x)
                if(miny>y)
                {
                    miny=y;
                    poz=i;
                }
    }
    for(i=poz;i<n;i++)L[i]=L[i+1];n--;
    for(i=1;i<=n;i++) muta(L[i].x,L[i].y);
    for(i=1;i<=n;i++) L[i].tg=atan2(L[i].y,L[i].x);
}
long double det(coord a,coord b,coord c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
void infasuratoare()
{
    int i;
    sol[0]=0;sol[1]=1;
    sf=1;
    for(i=2;i<=n;i++)
    {
        while(sf>=1&&det(L[sol[sf-1]],L[i],L[sol[sf]])<0)sf--;
        sol[++sf]=i;
    }
}
void afisare()
{
    int i;
    g<<sf+1<<'\n';
    minx=-minx;miny=-miny;
    for(i=0;i<=n;i++)muta(L[i].x,L[i].y);
    for(i=sf;i>=0;i--)
        g<<fixed<<setprecision(12)<<L[sol[i]].x<<" "<<L[sol[i]].y<<'\n';
}
int main()
{
   citire();
   sort(L+1,L+n+1,cmp);
   infasuratoare();
   afisare();
    return 0;
}