Pagini recente » Cod sursa (job #3347415) | Cod sursa (job #2370486) | Cod sursa (job #3308595) | Cod sursa (job #3345111) | Cod sursa (job #3301117)
#include <stdio.h>
#include <stdlib.h>
#define MAX 120005
typedef struct
{
double x, y;
} Punct;
Punct p[MAX],ch[2*MAX];
int n, h;
// compară două puncte pentru sortare lexicografică
int cmp(const void *a, const void *b)
{
Punct*p1=(Punct*)a;
Punct*p2=(Punct*)b;
if (p1->x<p2->x)
return -1;
if (p1->x>p2->x)
return 1;
if (p1->y<p2->y)
return -1;
if (p1->y>p2->y)
return 1;
return 0;
}
// produsul încrucișat
double orient(Punct a, Punct b, Punct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void convex_hull()
{
qsort(p, n, sizeof(Punct), cmp);
int i, t = 0;
// partea de jos
for (i = 0;i<n;i++)
{
while (h >= 2&&orient(ch[h-2],ch[h-1],p[i])<=0)
h--;
ch[h++]=p[i];
}
// partea de sus
t = h + 1;
for (i = n-2;i>=0;i--)
{
while (h>=t&&orient(ch[h-2],ch[h-1],p[i])<=0)
h--;
ch[h++] = p[i];
}
h--; // eliminăm ultimul punct (același cu primul)
}
int main() {
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
if(fin==NULL)
{
perror("eroare la deschiderea fisierului");
exit(-1);
}
if(fout==NULL)
{
perror("eroare la inchiderea fisierului");
exit(-1);
}
fscanf(fin, "%d", &n);
for (int i = 0; i < n; ++i)
fscanf(fin, "%lf %lf", &p[i].x, &p[i].y);
convex_hull();
fprintf(fout, "%d\n", h);
for (int i = 0; i < h; ++i)
fprintf(fout, "%.6lf %.6lf\n", ch[i].x, ch[i].y);
fclose(fin);
fclose(fout);
return 0;
}