Cod sursa(job #241526)
//scanarea Graham (n log n)
#include<stdio.h>
#include<algorithm>
const double maxV = 1000000001;
struct Pct {
double x;
double y;
};
using namespace std;
Pct a[120002];
int poz[120002];
int pInit;
int stack[120002];
int top;
int n;
bool cmp(int i, int j)
{
return ((a[j].y - a[pInit].y) * (a[i].x - a[pInit].x)) < ((a[j].x - a[pInit].x) * (a[i].y - a[pInit].y));
}
int CrossProd(int i, int j, int k)
{
return (((a[j].x - a[i].x) * (a[k].y - a[i].y) - (a[k].x - a[i].x) * (a[j].y - a[i].y)) > 0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
a[0].x = maxV;
a[0].y = maxV;
scanf("%d",&n);
pInit = 0;
for(int i = 1; i <= n; i++)
{
scanf("%lf %lf", &a[i].x, &a[i].y);
if (a[i].x < a[pInit].x)
{
if (pInit)
poz[++poz[0]] = pInit;
pInit = i;
}
else
if (a[i].x == a[pInit].x && a[i].y < a[pInit].y)
{
if (pInit)
poz[++poz[0]] = pInit;
pInit = i;
}
else
poz[++poz[0]] = i;
}
sort(poz + 1, poz + poz[0] + 1, cmp);
stack[1] = pInit;
stack[2] = poz[1];
top = 2;
for(int i = 2; i < n; i++)
{
while (CrossProd(stack[top], stack[top-1], poz[i]) == 0) top--;
top++;
stack[top] = poz[i];
}
printf("%d\n",top);
for(int i = top; i >= 1; i--)
printf("%lf %lf\n", a[stack[i]].x, a[stack[i]].y);
return 0;
}