Pagini recente » Cod sursa (job #1570320) | Cod sursa (job #1565479) | Cod sursa (job #2866015) | Cod sursa (job #1021032) | Cod sursa (job #448213)
Cod sursa(job #448213)
#include <stdio.h>
#include <algorithm>
#define per pair<double, double>
#define x first
#define y second
#define MAXN 120010
#define EPS 1e-12
using namespace std;
per a[MAXN];
int st[MAXN];
bool fol[MAXN];
int i,n;
inline int cmp(double a, double b)
{
if (a+EPS < b) return -1;
if (b+EPS < a) return 1;
return 0;
}
inline int det(per a, per b, per c)
{
return cmp(a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x, 0.0);
}
void Infasuratoare()
{
int poz, pas;
sort(a+1,a+n+1);
memset(fol, false, sizeof(fol));
st[++st[0]] = 1;
st[++st[0]] = 2;
fol[2] = true;
poz = 3; pas = 1;
while (!fol[1]){
while (fol[poz]){
if (poz == n)
pas = -1;
poz +=pas;
}
while (st[0]>=2 && det(a[st[st[0]]], a[st[st[0]-1]], a[poz]) == -1){
fol[st[st[0]]] = false;
st[0] --;
}
st[++st[0]] = poz;
fol[poz] = true;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%lf %lf",&a[i].x, &a[i].y);
Infasuratoare();
printf("%d\n", st[0]-1);
for (i=st[0]-1; i; i--)
printf("%.6lf %.6lf\n", a[st[i]].x, a[st[i]].y);
return 0;
}