Cod sursa(job #1166367)

Utilizator span7aRazvan span7a Data 3 aprilie 2014 15:11:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#define M 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct coord
{
    long double x,y;
    long double tg;
};
coord L[200001];
long double minx=M,miny=M;
int stiv[200001],n,sf;
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 xx,yy;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>xx>>yy;
        L[i].x=xx;
        L[i].y=yy;
        if(minx>xx)
            {
                minx=xx;
                miny=yy;
                poz=i;
            }
        else
            if(minx==xx)
                if(miny>yy)
                {
                    miny=yy;
                    poz=i;
                }
    }
    swap(L[n],L[poz]);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);
    sort(L+1,L+n+1,cmp);
}
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;
    stiv[1]=1;sf=1;
    for(i=2;i<=n;i++)
    {
        while(sf>=1&&det(L[stiv[sf-1]],L[i],L[stiv[sf]])<0)sf--;
        stiv[++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[stiv[i]].x<<" "<<L[stiv[i]].y<<'\n';
}
int main()
{
    citire();
    infasuratoare();
    afisare();
    return 0;
}