Cod sursa(job #541998)
#include <stdio.h>
#include <algorithm>
#define N 120001
using namespace std;
int n;
int top;
int top2;
int stack[N];
int stackd[N];
struct Punct {
double x;
double y;
};
Punct sir[N];
bool cmp(Punct i, Punct j) {
return i.x < j.x;
}
bool cmpy(Punct i, Punct j) {
return i.y < j.y;
}
int CrossProd(int i, int j, int k)
{
return (((sir[j].x - sir[i].x) * (sir[k].y - sir[i].y) - (sir[k].x - sir[i].x) * (sir[j].y - sir[i].y)) <= 0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++) {
double xp,yp;
scanf("%lf %lf",&xp,&yp);
sir[i].x = xp;
sir[i].y = yp;
}
sort(sir + 1, sir + n + 1, cmp);
int i = 1;
while (i <= n) {
int j = i;
while (sir[j].x == sir[j+1].x && j < n) j++;
if (j != i) {
sort(sir + i, sir + j, cmpy);
}
i = j + 1;
}
stack[1] = 1;
stack[2] = 2;
top = 2;
for(int i = 3; i <= n; i++) {
while (CrossProd(stack[top], i, stack[top - 1]) == 0) top--;
stack[++top] = i;
}
stackd[1] = n;
stackd[2] = n - 1;
top2 = 2;
for(int i = n - 2; i > 0; i--) {
while (CrossProd(stackd[top2], i, stackd[top2 - 1]) == 0) top2--;
stackd[++top2] = i;
}
printf("%d\n",top + top2 - 2);
for(int i = top; i > 0; i--)
printf("%lf %lf\n",sir[stack[i]].x, sir[stack[i]].y);
for(int i = top2 - 1; i > 1; i--)
printf("%lf %lf\n",sir[stackd[i]].x, sir[stackd[i]].y);
return 0;
}