Pagini recente » Cod sursa (job #2410915) | Cod sursa (job #1632618) | Cod sursa (job #534989) | Cod sursa (job #2468241) | Cod sursa (job #3233064)
#include <stdio.h>
#define MAXN 120000
#define MAXY 1000000000
#define EPSILON 0.000000000001
long double x[MAXN], y[MAXN];
char viz[MAXN];
int stiva[MAXN];
static inline int compare(int a, int b) {
if (x[a] == x[b])
return y[a] < y[b];
return x[a] < x[b];
}
void myqsort(int begin, int end) {
int b = begin - 1, e = end + 1, pivot = (begin + end) / 2;
long double aux;
while (compare(++b, pivot));
while (compare(pivot, --e));
while (b < e) {
aux = x[b];
x[b] = x[e];
x[e] = aux;
aux = y[b];
y[b] = y[e];
y[e] = aux;
while (compare(++b, pivot));
while (compare(pivot, --e));
}
if (begin < e)
myqsort(begin, e);
if (e + 1 < end)
myqsort(e + 1, end);
}
static inline long double det(int a, int b, int c) {
return x[a] * (y[b] - y[c]) + x[b] * (y[c] - y[a]) + x[c] * (y[a] - y[b]);
}
int main() {
FILE *fin, *fout;
int n, i, sp, oldsp;
fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for (i = 0; i < n; i++)
fscanf(fin, "%Lf%Lf", &x[i], &y[i]);
fclose(fin);
myqsort(0, n - 1);
sp = 0;
for (i = 0; i < n; i++) {
while (sp > 1 && det(stiva[sp - 1], stiva[sp - 2], i) < EPSILON)
sp--;
stiva[sp++] = i;
}
oldsp = sp;
for (i = n - 1; i >= 0; i--) {
while (sp > oldsp && det(stiva[sp - 1], stiva[sp - 2], i) < EPSILON)
sp--;
stiva[sp++] = i;
}
sp--;
fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", sp);
for (i = 0; i < sp; i++)
fprintf(fout, "%.12Lf %.12Lf\n", x[stiva[i]], y[stiva[i]]);
fclose(fout);
return 0;
}