Pagini recente » Borderou de evaluare (job #1036217) | Cod sursa (job #1991477) | Cod sursa (job #2969504) | Cod sursa (job #2767503) | Cod sursa (job #2014999)
#include <cstdio>
#include <algorithm>
FILE *fin, *fout;
#define MAXN 120000
struct at {
double x;
double y;
};
int N;
at v[MAXN + 1];
int sti[MAXN + 1];
bool viz[MAXN + 1];
int i1, i0;
int d1, d0;
const double inf = 0.000000001;
bool cmp(at a, at b) {
if (a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
inline double ver(at i, at st, at dr) {
return (st.x - i.x) * (dr.y - i.y) - (st.y - i.y) * (dr.x - i.x);
}
int main() {
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
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, cmp);
int stid = 2;
sti[1] = 1;
sti[2] = 2;
for (int i = 1; i <= N; i++) {
if (viz[i])
continue;
while (stid >= 2 && ver(v[sti[stid - 1]], v[sti[stid]], v[i]) < inf)
viz[sti[stid--]] = 0;
sti[++stid] = i;
viz[i] = 1;
}
for (int i = N - 1; i > 0; i--) {
if (viz[i])
continue;
while (stid >= 2 && ver(v[sti[stid - 1]], v[sti[stid]], v[i]) < inf)
viz[sti[stid--]] = 0;
sti[++stid] = i;
viz[i] = 1;
}
fprintf(fout, "%d\n", stid - 1);
for (int i = 1; i <= stid - 1; i++)
fprintf(fout, "%lf %lf\n", v[sti[i]].x, v[sti[i]].y);
fclose(fin);
fclose(fout);
return 0;
}