Cod sursa(job #1091354)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 25 ianuarie 2014 17:09:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <cmath>
#include <cstdio>
#include <stack>
#include <iomanip>
#include <algorithm>
#define Precizie 1000000000000
#define eps 0.000000000001
#define oo 2000000000
#define Nmax 120099
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N,one,k;

struct point {long double x,y;}P[Nmax],st[Nmax];

inline long double CrossProduct(const point &A,const point &B,const point &C)
{
    return (A.x-B.x)*(C.y-B.y)-(C.x-B.x)*(A.y-B.y);
}

inline bool Equal(const long double &x,const long double &y)
{
    if(fabs(x-y)<eps)return 1;
    else return 0;
}

inline bool LessThan(const long double &x,const long double &y)
{
    if(1LL*Precizie*x<1LL*Precizie*y)return 1;
    else return 0;
}


struct cmp
{
    bool operator()(const point &A,const point &B)const
    {
        return LessThan(CrossProduct(P[1],A,B),0);
    };
};




int main()
{
    f>>N;
    for(int i=1;i<=N;++i)
    {
        //long double x,y;
        //f>>x>>y;
        //P[i].x=x*Precizie; P[i].y=y*Precizie;
        f>>P[i].x>>P[i].y;
    }
    one=1;
    for(int i=2;i<=N;++i)
        if(LessThan(P[i].y,P[one].y))one=i;
        else if(Equal(P[i].y,P[one].y) && LessThan(P[i].x,P[one].x))one=i;
    swap(P[1],P[one]);
    sort(P+1,P+N,cmp());
    //for(int i=1;i<=N;++i)g<<P[i].x<<' '<<P[i].y<<'\n';
    st[1]=P[1],st[2]=P[2]; k=2;
    for(int i=3;i<=N;++i)
    {
        while(k>=2 && CrossProduct(st[k-1],st[k],P[i])>0)--k;
        st[++k]=P[i];
    }
    g<<k<<'\n';
    for(int i=1;i<=k;++i)g<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}