Pagini recente » Cod sursa (job #2706124) | Cod sursa (job #3265438) | Cod sursa (job #2851797) | Cod sursa (job #3041109) | Cod sursa (job #1166363)
#include <algorithm>
#include <cstdio>
using namespace std;
#define fi first
#define se second
typedef pair<double, double> pdd;
const int MaxN = 120050;
int n;
pdd p[MaxN];
inline double determinant(const pdd &a, const pdd &b, const pdd &c) {
return a.fi * b.se + b.fi * c.se + c.fi * a.se - a.se * b.fi - b.se * c.fi - c.se * a.fi;
}
int sh, ss;
pdd hull[MaxN], stk[MaxN];
void make_hull() {
stk[ss = 1] = p[1];
stk[++ss] = p[2];
for (int i = 3; i <= n; ++i) {
while (ss > 1 && determinant(stk[ss - 1], stk[ss], p[i]) < 0)
--ss;
stk[++ss] = p[i];
}
for (int i = 1; i < ss; ++i)
hull[++sh] = stk[i];
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].fi, &p[i].se);
sort(p + 1, p + n + 1);
make_hull();
reverse(p + 1, p + n + 1);
make_hull();
printf("%d\n", sh);
for (int i = 1; i <= sh; ++i)
printf("%.6lf %.6lf\n", hull[i].fi, hull[i].se);
}