Pagini recente » Cod sursa (job #3310714) | Statistici Tamas Vlad (vlad19alex) | Cod sursa (job #3325281) | Statistici Nicolae Bold (nicuuss) | Cod sursa (job #3359399)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} pct;
int comparePoints(const void* a,const void* b) {
pct* p1=(pct*)a;
pct* p2=(pct*)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 crossProduct(pct a,pct b,pct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main()
{
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
if (!fin || !fout) return 0;
int n;
if (fscanf(fin,"%d",&n)!=1) return 0;
pct* points=(pct*)malloc(n*sizeof(pct));
for (int i=0;i<n;++i)
{
fscanf(fin,"%lf %lf",&points[i].x,&points[i].y);
}
qsort(points,n,sizeof(pct),comparePoints);
pct* hull=(pct*)malloc(2*n*sizeof(pct));
int h_size=0;
for (int i=0;i<n;++i)
{
while (h_size>=2 && crossProduct(hull[h_size-2],hull[h_size-1],points[i])<=1e-11)
{
h_size--;
}
hull[h_size++]=points[i];
}
int lower_size=h_size;
for (int i=n-2;i>=0;--i)
{
while (h_size>lower_size && crossProduct(hull[h_size-2],hull[h_size-1],points[i])<= 1e-11)
{
h_size--;
}
hull[h_size++]=points[i];
}
if (h_size>1) h_size--;
int start_idx = 0;
for (int i=1;i<h_size;++i)
if (hull[i].y> < hull[start_idx].y || (hull[i].y == hull[start_idx].y && hull[i].x < hull[start_idx].x)) start_idx = i;
fprintf(fout,"%d\n",h_size);
for (int i=0; i<h_size;++i)
{
int idx=(start_idx+i) % h_size;
fprintf(fout,"%.6f %.6f\n",hull[idx].x,hull[idx].y);
}
free(points);
free(hull);
fclose(fin);
fclose(fout);
return 0;
}