Pagini recente » Cod sursa (job #2802171) | Cod sursa (job #824580) | Cod sursa (job #2859524) | Cod sursa (job #355416) | Cod sursa (job #3300912)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 120000
typedef struct{
double x,y;
}point;
point points[MAX], infasuratoare[MAX];
int N, top=0;
// aici gasim indexul punctului de start pentru infasuratoarea noastra
int find_starting_point()
{
int idx=0;
for(int i=1; i<N; i++)
{
if((points[i].y < points[idx].y)|| (points[i].y == points[idx].y && points[i].x < points[idx].x))
{
idx=i;
}
}
return idx;
}
//aici verificam sensul rotirii la 3 unghiuri
double cross(point a, point b, point c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
//aici facem functia de comparatie pentru sortarea punctelor ramase fata de unghiul format cu punctul de start
int compare(const void *x, const void *y)
{
point p1=*(point*)x;
point p2=*(point*)y;
double val=cross(points[0], p1,p2);
if(val==0)
{
double d1 = (p1.x - points[0].x)*(p1.x - points[0].x) + (p1.y - points[0].y)*(p1.y - points[0].y);
double d2 = (p2.x - points[0].x)*(p2.x - points[0].x) + (p2.y - points[0].y)*(p2.y - points[0].y);
if(d1<d2)
return -1;
else return 1;
}
if(val>0)
return -1;
else return 1;
}
void graham()
{
int start=find_starting_point();
point aux=points[0];
points[0]=points[start];
points[start]=aux;
qsort(points+1,N-1,sizeof(point), compare);
infasuratoare[0]=points[0];
infasuratoare[1]=points[1];
top=2;
for (int i=2; i<N; i++)
{
while (top>=2&&cross(infasuratoare[top-2],infasuratoare[top-1], points[i]) <= 0)
top--;
infasuratoare[top++] = points[i];
}
}
int main(void)
{
FILE *fin=NULL, *fout=NULL;
if((fin=fopen("infasuratoare.in","r"))==NULL)
{
fprintf(stderr,"eroare la deschidere fisier");
exit(-1);
}
if((fout=fopen("infasuratoare.out","w"))==NULL)
{
fprintf(stderr,"eroare la deschidere fisier");
exit(-1);
}
fscanf(fin,"%d", &N);
for(int i=0; i<N; i++)
{
fscanf(fin,"%lf %lf", &points[i].x, &points[i].y);
}
graham();
fprintf(fout,"%d\n",top);
for(int i=0; i<top; i++)
{
fprintf(fout,"%.6lf %.6lf\n", infasuratoare[i].x, infasuratoare[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}