Pagini recente » Cod sursa (job #786976) | Cod sursa (job #2043940) | Diferente pentru teorema-chineza-a-resturilor intre reviziile 24 si 25 | Monitorul de evaluare | Cod sursa (job #2014997)
#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.000001;
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;
viz[2] = 1;
viz[1] = 1;
for (int i = 1; i <= N; i++) {
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--) {
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);
for (int i = 1; i <= stid; i++)
fprintf(fout, "%lf %lf\n", v[i].x, v[i].y);
fclose(fin);
fclose(fout);
return 0;
}