Cod sursa(job #1103531)

Utilizator DaniEsDani Stetcu DaniEs Data 9 februarie 2014 18:39:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct{
    double x, y;
};
Punct P[NMax], S[NMax];
int N, k;
inline double Area(Punct A, Punct B, Punct C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x;
}
inline int cmp(Punct A, Punct B)
{
    if(Area(P[1], A, B)>0)
        return 1;
    return 0;
}
void Read()
{
    fin>>N;
    for(int i=1; i<=N; i++)
        fin>>P[i].x>>P[i].y;
    int Min=1;
    for(int i=2; i<=N; i++)
        if(P[i].y<P[Min].y || (P[i].y==P[Min].y && P[Min].x>P[i].x))
            Min=i;
    swap(P[1], P[Min]);
    sort(P+2, P+N+1, cmp);
}
void Solve()
{
    S[1]=P[1];
    S[2]=P[2];
    k=2;
    for(int i=3; i<=N; i++)
    {
        while(k>=2 && Area(S[k-1], S[k], P[i])<0)
            k--;
        S[++k]=P[i];
    }

}
void Print()
{
    fout<<k<<'\n';
    for(int i=1; i<=k; i++)
        fout<<fixed<<setprecision(9)<<S[i].x<<" "<<S[i].y<<'\n';
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}