Pagini recente » Statistici Buzdea Matei (matei.buzdea) | Statistici Velicu Teodora (DoraBenzo) | Monitorul de evaluare | Clasament dupa rating | Cod sursa (job #2014932)
#include <cstdio>
#include <algorithm>
FILE *fin, *fout;
#define MAXN 120000
struct at {
double x;
double y;
};
int N;
at v[MAXN + 1];
at p1[MAXN + 1], p0[MAXN + 1];
int inf1[MAXN + 1], inf0[MAXN + 1];
double Cos1[MAXN + 1], Cos0[MAXN + 1];
int i1, i0;
int d1, d0;
const double inf = 0.000001;
bool cmp(at a, at b) {
return a.x < b.x;
}
inline bool ver(int i, int st, int dr) {
if (abs(v[st].x - v[dr].x) < inf) {
if (v[i].x > v[st].x)
return 0;
else
return 1;
}
else if (abs(v[st].y - v[dr].y) < inf) {
if (v[i].y > v[st].y)
return 1;
else
return 0;
}
else {
double A = (v[st].x - v[dr].x) / (v[st].y - v[dr].y);
double B = A * v[st].x - v[st].y;
double Y;
Y = A * v[i].x + B;
if ((Y - v[i].y) < 0.0)
return 1;
else
return 0;
}
}
int main() {
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &N);
int st, dr;
st = dr = 1;
fscanf(fin, "%lf%lf", &v[1].x, &v[1].y);
for (int i = 2; i <= N; i++) {
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
if (v[i].x < v[st].x) {
st = i;
}
if (v[i].x > v[dr].x) {
dr = i;
}
}
for (int i = 1; i <= N; i++) {
if (i != st && i != dr) {
if (ver(i, st, dr) == 1) {
p1[++i1].x = v[i].x;
p1[i1].y = v[i].y;
}
else {
p0[++i0].x = v[i].x;
p0[i0].y = v[i].y;
}
}
}
std::sort(p1 + 1, p1 + i1 + 1, cmp);
std::sort(p0 + 1, p0 + i0 + 1, cmp);
for (int i = 1; i <= i0; i++) {
double l1, l2, l3;
l1 = (v[dr].x - v[st].x) * (v[dr].x - v[st].x) +
(v[dr].y - v[st].y) * (v[dr].y - v[st].y);
l3 = (v[dr].x - p0[i].x) * (v[dr].x - p0[i].x) +
(v[dr].y - p0[i].y) * (v[dr].y - p0[i].y);
l2 = (v[st].x - p0[i].x) * (v[st].x - p0[i].x) +
(v[dr].y - p0[i].y) * (v[dr].y - p0[i].y);
double Cos;
Cos = (-l3 + l1 + l2) / sqrt(4.0 * l1 * l2);
Cos0[i] = Cos;
while (d0 > 0 && Cos0[inf0[d0]] > Cos)
d0--;
inf0[++d0] = i;
}
for (int i = 1; i <= i1; i++) {
double l1, l2, l3;
l1 = (v[dr].x - v[st].x) * (v[dr].x - v[st].x) +
(v[dr].y - v[st].y) * (v[dr].y - v[st].y);
l3 = (v[dr].x - p1[i].x) * (v[dr].x - p1[i].x) +
(v[dr].y - p1[i].y) * (v[dr].y - p1[i].y);
l2 = (v[st].x - p1[i].x) * (v[st].x - p1[i].x) +
(v[dr].y - p1[i].y) * (v[dr].y - p1[i].y);
double Cos;
Cos = (-l3 + l1 + l2) / sqrt(4.0 * l1 * l2);
Cos1[i] = Cos;
while (d1 > 0 && Cos1[inf1[d1]] > Cos) {
d1--;
}
inf1[++d1] = i;
}
fprintf(fout, "%d\n", d1 + d0 + 2);
fprintf(fout, "%lf %lf\n", v[st].x, v[st].y);
for (int i = 1; i <= d0; i++)
fprintf(fout, "%lf %lf\n", p0[inf0[i]].x, p0[inf0[i]].y);
fprintf(fout, "%lf %lf\n", v[dr].x, v[dr].y);
for (int i = d1; i >= 1; i--)
fprintf(fout, "%lf %lf\n", p1[inf1[i]].x, p1[inf1[i]].y);
fclose(fin);
fclose(fout);
return 0;
}