Pagini recente » Cod sursa (job #1290137) | Cod sursa (job #1184198) | Cod sursa (job #954761) | Cod sursa (job #1282877) | Cod sursa (job #1524081)
#include <bits/stdc++.h>
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
#define x first
#define y second
#define eps 0.000000000001
using namespace std;
typedef pair<double, double> pereche;
int n, m, q, i;
pereche v[120005], r[120005];
double arie;
int stv[120005];
double det(pereche A, pereche B, pereche C)
{
double r = A.x * B.y - A.y * B.x + B.x * C.y - C.x * B.y + C.x * A.y - A.x * C.y;
return r;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1);
m = 2;
stv[1] = 1;
stv[2] = 2;
for(i = 3; i <= n; i++)
{
while(m > 1 && det(v[ stv[m - 1] ], v[ stv[m] ], v[i]) < eps)
m--;
stv[++m] = i;
}
q = m;
for(i = 1; i <= q; i++)
r[i] = v[ stv[i] ];
m = 2;
stv[1] = n;
stv[2] = n - 1;
for(i = n - 2; i >= 1; i--)
{
while(m > 1 && det(v[ stv[m - 1] ], v[ stv[m] ], v[i]) < eps)
m--;
stv[++m] = i;
}
for(i = 1; i <= m; i++)
r[ ++q ] = v[ stv[i] ];
/*arie = 0;
for(i = 1; i < q; i++)
arie += v[i].x * v[i + 1].y - v[i].y * v[i + 1].x;
arie /= 2.0;
printf("%.12f", arie);*/
printf("%d\n", q - 2);
for(i = 1; i < q; i++)
{
if(r[i] == r[i - 1] && i > 1)
continue;
printf("%.6f %.6f\n", r[i].x, r[i].y);
}
return 0;
}