Pagini recente » Cod sursa (job #2363918) | Cod sursa (job #2394067) | Cod sursa (job #178805) | Cod sursa (job #2406318) | Cod sursa (job #1410636)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
typedef pair<double, double> punct;
punct v[120001], a[100001], xmin, xmax, ymin, ymax;
int n, i, nr, st[100001], k, s;
bool U[100001];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double isLeft(punct p0, punct p1, punct p2)
{ return (p2.x-p0.x)*(p1.y-p0.y)-(p2.y-p0.y)*(p1.x-p0.x);
}
int main()
{ f>>n;
for (i=1; i<=n; ++i)
{ f>>v[i].x>>v[i].y;
if (i==1)
xmin=xmax=ymin=ymax=v[i];
else
{ if (xmin.x>v[i].x)
xmin=v[i];
if (xmax.x<v[i].x)
xmax=v[i];
if (ymin.y>v[i].y)
ymin=v[i];
if (ymax.y<v[i].y)
ymax=v[i];
}
}
for (i=1; i<=n; ++i)
if (isLeft(ymin, xmax, v[i])>=0 || isLeft(xmax, ymax, v[i])>=0 || isLeft(ymax, xmin, v[i])>=0 || isLeft(xmin, ymin, v[i])>=0)
a[++nr]=v[i];
sort(a+1, a+nr+1);
st[1]=1;
st[2]=2;
U[2]=1;
k=2;
for (i=3, s=1; i>0; i+=(s=(i==nr? -s:s)))
if (!U[i])
{ while (k>=2 && isLeft(a[st[k-1]], a[st[k]], a[i])>0)
U[st[k--]]=0;
st[++k]=i;
U[i]=1;
}
g<<k-1<<'\n';
g<<setprecision(6)<<fixed;
for (i=1; i<k; ++i)
g<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
return 0;
}