Cod sursa(job #909855)
#include <cstdio>
#include <algorithm>
#define NMAX 120002
#define INF (1 << 30)
using namespace std;
struct punct
{
double x;
double y;
double p;
}a[NMAX];
int n;
int h = 2;
int q[NMAX];
bool cmp(punct a, punct b)
{
if(a.p < b.p || a.p == b.p && a.y > b.y)
return 1;
return 0;
}
double panta(double x, double y)
{
if(x == 0)
return INF;
return y / x;
}
void read()
{
freopen("infasuratoare.in", "r", stdin);
scanf("%d\n", &n);
for(int i = 0; i < n; ++ i)
{
scanf("%lf %lf\n", &a[i].x, &a[i].y);
a[i].p = panta(a[i].x, a[i].y);
}
}
double det(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
void solve()
{
q[0] = 0;
q[1] = 1;
for(int i = 2; i < n; ++ i)
{
while(det(a[q[h - 2]], a[q[h - 1]], a[i]) <= 0)
-- h;
q[h ++] = i;
}
}
void write()
{
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", h);
for(int i = 0; i < h; ++ i)
printf("%lf %lf\n", a[q[i]].x, a[q[i]].y);
}
int main()
{
read();
sort(a, a + n, cmp);
solve();
write();
return 0;
}