Pagini recente » Cod sursa (job #2756478) | Cod sursa (job #666354) | Cod sursa (job #2741830) | Cod sursa (job #917639) | Cod sursa (job #3359310)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x,y;
}punct;
punct pivot;
double produs(punct o,punct a,punct b)
{
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double dist_sq(punct p1, punct p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int compareunghi(const void *vp1, const void *vp2)
{
punct *p1=(punct *)vp1;
punct *p2=(punct*)vp2;
double cp=produs(pivot, *p1, *p2);
if (cp>1e-12)
return -1;
if (cp < -1e-12)
return 1;
double d1=dist_sq(pivot, *p1);
double d2=dist_sq(pivot, *p2);
if (d1 < d2)
return -1;
if (d1 > d2)
return 1;
return 0;
}
int main()
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
punct *pts=(punct*)malloc(n * sizeof(punct));
for (int i=0;i<n;++i)
fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
int pivot_idx = 0;
for (int i=1;i<n;i++)
{
if (pts[i].y<pts[pivot_idx].y || (pts[i].y==pts[pivot_idx].y && pts[i].x<pts[pivot_idx].x))
pivot_idx=i;
}
punct temp = pts[0];
pts[0] = pts[pivot_idx];
pts[pivot_idx] = temp;
pivot = pts[0];
qsort(&pts[1],n-1,sizeof(punct),compareunghi);
punct *hull=(punct *)malloc(n*sizeof(punct));
int top = 0;
hull[top++]=pts[0];
if (n > 1)
hull[top++]=pts[1];
for (int i = 2; i < n; i++)
{
while (top>=2 && produs(hull[top-2],hull[top-1],pts[i])<=1e-12)
top--;
hull[top++]=pts[i];
}
fprintf(fout, "%d\n", top);
for (int i = 0; i < top; i++)
fprintf(fout,"%.6lf %.6lf\n",hull[i].x,hull[i].y);
fclose(fin);
fclose(fout);
free(pts);
free(hull);
return 0;
}