Pagini recente » Cod sursa (job #1643058) | Cod sursa (job #434797) | Cod sursa (job #1436887) | Cod sursa (job #1606401) | Cod sursa (job #3300771)
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef struct point{
double x, y;
} point;
point min;
double angle( point a , point b, point c )
{
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
double slope( point a, point b )
{
if ( a.x == b.x )
{
if ( a.y < b.y )
return INFINITY;
else
return -INFINITY;
}
else
return (b.y-a.y)/(b.x-a.x);
}
int cmp( const void* a, const void* b )
{
point *c = (point *)a;
point *d = (point *)b;
if ( slope(min,*c) > slope (min,*d) )
return 1;
if ( slope(min,*c) == slope (min,*d) )
{
if ( c->x > d->x )
return 1;
if ( c->x == d->x )
{
if ( c->y > d->y )
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
int main(void)
{
FILE *f,*out;
f = fopen("infasuratoare.in","r");
out = fopen("infasuratoare.out","w");
int n;
point v[120001];
fscanf(f,"%d",&n);
for ( int i = 0 ; i < n ; i++ )
{
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
if ( v[i].x < min.x || i == 0 )
{
min = v[i];
}
if ( v[i].x == min.x && v[i].y == min.y )
{
min.y = v[i].y;
}
}
qsort(v,n,sizeof(point),cmp);
point st[120001];
int k = 2,i = 2;
st[0] = v[0];
st[1] = v[1];
while ( i < n )
{
while ( angle(st[k-2],st[k-1],v[i]) <= 0 && k >= 2 )
{
k--;
}
st[k] = v[i];
k++;
i++;
}
fprintf(out,"%d\n",k);
for ( int j = 0 ; j < k ; j++ )
{
fprintf(out,"%.12lf %.12lf \n",st[j].x,st[j].y);
}
fclose(out);
fclose(f);
return 0;
}