Cod sursa(job #613358)
#include <cstdio>
#include <algorithm>
#define N 120005
#define inf 1000000005
using namespace std;
struct punct
{
double x, y, p;
} a[N], c, st[N];
int n, poz;
bool cmp(punct a, punct b)
{
if (a.p > b.p)
return false;
return true;
}
void citire()
{
scanf ("%d ", &n);
c.x = c.y = inf;
for (int i = 0; i < n; ++ i)
{
scanf ("%lf %lf ", &a[i].x, &a[i].y);
if (a[i].x < c.x || a[i].x == c.x && a[i].y < c.y)
{
c.x = a[i].x;
c.y = a[i].y;
poz = i;
}
}
a[poz] = a[n-1];
-- n;
}
void pante()
{
for (int i = 0; i < n; ++i)
{
if (a[i].x == c.x)
a[i].p = inf;
else
a[i].p = (a[i].y - c.y) / (a[i].x - c.x);
}
}
bool det(punct a, punct b, punct c)
{
double rez = a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
if (rez >= 0)
return true;
return false;
}
void stiva()
{
st[0] = c;
st[1] = a[0];
int m = 2;
for (int i = 1; i < n; ++ i)
{
bool x = det (st[m-2], st[m-1], a[i]);
if (x)
st[m ++] = a[i];
else
{
while(!det (st[m-2], st[m-1], a[i]))
st[-- m] = a[i];
++ m;
}
}
printf ("%d\n", m);
for (int i = 1; i < m; ++ i)
printf ("%lf %lf\n", st[i].x, st[i].y);
printf ("%lf %lf\n", c.x, c.y);
}
int main()
{
freopen ("infasuratoare.in", "r", stdin);
///freopen ("infasuratoare.out", "w", stdout);
citire();
pante();
sort (a, a+n, cmp);
stiva();
return 0;
}