Pagini recente » Cod sursa (job #1321855) | Monitorul de evaluare | Cod sursa (job #927334) | Borderou de evaluare (job #1322625) | Cod sursa (job #3358138)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Punct;
int comp(const void *a, const void *b) {
const Punct *p1 = a;
const Punct *p2 = b;
if (p1->x != p2->x)
return (p1->x > p2->x) ? 1 : -1;
if (p1->y != p2->y)
return (p1->y > p2->y) ? 1 : -1;
return 0;
}
double cross(Punct A, Punct B, Punct C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int main() {
FILE *fin = NULL;
fin = fopen("infasuratoare.in", "r");
if(fin == NULL)
return -1;
int N;
fscanf(fin,"%d", &N);
Punct *puncte = malloc(N * sizeof(Punct));
for(int i = 0; i < N; i ++)
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
qsort(puncte, N, sizeof(Punct), comp);
Punct *st = malloc(2 * N * sizeof(Punct));
int k = 0;
for(int i = 0;i < N; i ++) {
while(k > 1 && cross(st[k-2], st[k-1], puncte[i]) <= 0)
k--;
st[k] = puncte[i];
k ++;
}
int li = k+1;
for(int i = N-2; i >= 0; i--) {
while(k >= li && cross(st[k-2], st[k-1], puncte[i]) <= 0)
k --;
st[k] = puncte[i];
k ++;
}
k --;
FILE *fout = NULL;
fout = fopen("infasuratoare.out", "w");
if(fout == NULL) {
free(puncte);
free(st);
return -1;
}
fprintf(fout, "%d\n", k);
for(int i = 0; i < k; i ++)
fprintf(fout, "%lf %lf\n", st[i].x, st[i].y);
free(puncte);
free(st);
fclose(fin);
return 0;
}