Pagini recente » Cod sursa (job #437558) | Cod sursa (job #2109324) | Rating Sargu Irina (irina.sargu) | Cod sursa (job #2006955) | Cod sursa (job #2051376)
#include <cstdio>
#include <algorithm>
#include <cmath>
FILE *fin = fopen("infasuratoare.in", "r"), *fout = fopen("infasuratoare.out", "w");
#define MAXN 120000
#define EPS 0.00000001
struct myc {
double x, y;
inline bool operator < (const myc &u) const {
if (std::fabs(x - u.x) > EPS) return x < u.x;
else return y < u.y;
}
} v[MAXN + 1];
int st[MAXN + 1];
inline double arie(myc a, myc b, myc c) {
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}
int main() {
int n;
fscanf(fin, "%d", &n);
for (int i = 1; i <= n; i++)
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
std::sort(v + 1, v + n + 1);
int vf = 0;
for (int i = 1; i <= n; i++) {
while (vf > 1 && arie(v[st[vf - 1]], v[st[vf]], v[i]) < EPS)
vf--;
st[++vf] = i;
}
int l = vf;
for (int i = n - 1; i > 0; i--) {
while (vf > l && arie(v[st[vf - 1]], v[st[vf]], v[i]) < EPS)
vf--;
if (i != 1)
st[++vf] = i;
}
fprintf(fout, "%d\n", vf);
for (int i = 1; i <= vf; i++)
fprintf(fout, "%.8f %.8f\n", v[st[i]].x, v[st[i]].y);
fclose(fin);
fclose(fout);
return 0;
}