Pagini recente » Cod sursa (job #1231012) | Cod sursa (job #2000581) | Cod sursa (job #1997513) | Cod sursa (job #2732972) | Cod sursa (job #1822769)
#include <cstdio>
#include <algorithm>
const int MAX_N = 120000;
struct Punct {
double x, y;
}v[MAX_N];
int top1, top2;
int upper[MAX_N];
int lower[MAX_N];
bool cmp(Punct a, Punct b) {
return a.x < b.x;
}
double ccw(Punct a, Punct b, Punct c) {
return a.x * b.y +
b.x * c.y +
c.x * a.y -
a.x * c.y -
b.x * a.y -
c.x * b.y;
}
int main() {
int n;
FILE *fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for(int i = 0; i < n; ++i)
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
fclose(fin);
std::sort(v, v + n, cmp);
top1 = 0;
for(int i = 0; i < n; ++i) {
while(top1 >= 2 && ccw(v[i], v[lower[top1 - 1]], v[lower[top1 - 2]]) > 0)
top1--;
lower[top1] = i;
top1++;
}
top2 = 0;
for(int i = 0; i < n; ++i) {
while(top2 >= 2 && ccw(v[i], v[upper[top2 - 1]], v[upper[top2 - 2]]) < 0)
top2--;
upper[top2] = i;
top2++;
}
FILE *fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", top1 + top2 - 2);
for(int i = 0; i < top1; ++i)
fprintf(fout, "%lf %lf\n", v[lower[i]].x, v[lower[i]].y);
for(int i = top2 - 2; i > 0; --i)
fprintf(fout, "%lf %lf\n", v[upper[i]].x, v[upper[i]].y);
fclose(fout);
return 0;
}