Pagini recente » Cod sursa (job #228542) | Cod sursa (job #1369951) | Cod sursa (job #2423742) | Cod sursa (job #1514700) | Cod sursa (job #714980)
Cod sursa(job #714980)
#include <algorithm>
#include <cstdio>
#include <cmath>
struct Vect {
float x, y;
void operator += (Vect v) {
x += v.x;
y += v.y;
}
void operator -= (Vect v) {
x -= v.x;
y -= v.y;
}
};
int points;
Vect point[120002];
#define px(i) point[i].x
#define py(i) point[i].y
void swap(int a, int b) {
Vect swap = point[a];
point[a] = point[b];
point[b] = swap;
}
bool cmp(Vect a, Vect b) {
return(atan2(a.y, a.x) < atan2(b.y, b.x));
}
bool ccw(int a, int b, int c) {
return((px(b) - px(a)) * (py(c) - py(a)) < (py(b) - py(a)) * (px(c) - px(a)));
}
int main() {
FILE * in = fopen("infasuratoare.in", "rt");
FILE * out = fopen("infasuratoare.out", "wt");
fscanf(in, "%d", &points);
int my = 1;
for (int i = 1; i <= points; ++i) {
fscanf(in, "%f%f", &point[i].x, &point[i].y);
if (py(i) < py(my)) {
my = i;
}
}
swap(1, my);
for (int i = 2; i <= points; ++i) {
point[i] -= point[1];
}
std::sort(point + 2, point + points + 1, cmp);
for (int i = 2; i <= points; ++i) {
point[i] += point[1];
}
int k = 1;
point[0] = point[points];
for (int i = 2; i <= points; ++i) {
while (ccw(k - 1, k, i)) {
--k;
}
++k;
swap(i, k);
}
fprintf(out, "%d\n", k);
for (int i = 1; i <= k; ++i) {
fprintf(out, "%f %f\n", point[i].x, point[i].y);
}
fclose(in);
fclose(out);
}