Cod sursa(job #1095339)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 30 ianuarie 2014 18:57:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
using namespace std;
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120005
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
  double x,y;
};
Punct P[NMax],S[NMax];
int N,k;
void Read()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>P[i].x>>P[i].y;
}
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)
{
    return Area(P[1],A,B)>0;
}
void Solve()
{
int Min=1;
for(int i=2;i<=N;i++)
    if(P[i].y<P[Min].y ||(P[i].y==P[Min].y && P[i].x<P[Min].x))
        Min=i;
swap(P[1],P[Min]);
sort(P+2,P+N+1,cmp);
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(6)<<S[i].x<<" "<<S[i].y<<"\n";
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}