Pagini recente » Cod sursa (job #2821088) | Cod sursa (job #2424148) | Cod sursa (job #1921995) | Cod sursa (job #558423) | Cod sursa (job #1408550)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second
using namespace std;
typedef pair<double, double> punct;
punct v[NMAX];
int n, i, j, st[NMAX], s, k;
bool U[NMAX];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double isLeft(punct p0, punct p1, punct p2)
{ return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
int main()
{ f>>n;
for (i=1; i<=n; ++i)
f>>v[i].x>>v[i].y;
sort(v+1, v+n+1);
st[1]=1;
st[2]=2;
k=2;
U[1]=U[2]=1;
for (i=1, s=1; i>0; i+=(s=(i==n? -s:s)))
if (!U[i])
{ while (k>=2 && isLeft(v[st[k]], v[st[k-1]], v[i])<0)
U[st[k--]]=0;
st[++k]=i;
U[i]=1;
}
g<<k<<'\n';
g<<setprecision(6)<<fixed;
for (i=1; i<=k; ++i)
g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
return 0;
}