Pagini recente » Cod sursa (job #3311911) | Cod sursa (job #3305894) | Cod sursa (job #3330058) | Cod sursa (job #3321568) | Cod sursa (job #3359027)
#include<stdio.h>
#include<stdlib.h>
#define EPS 1e-12
#define MAX 120000
typedef struct{
double x;
double y;
}Point;
int comparare(const void *a,const void *b)
{
const Point *p1=(const Point *)a;
const Point *p2=(const Point *)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;
}
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);
}
int main()
{
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
if(f==NULL || g==NULL)
{
perror("eroare deschidere fisier");
return 1;
}
int n;
static Point puncte[MAX];
static Point stiva[2*MAX+5];
if(fscanf(f,"%d",&n)!=1)
{
printf("citire incorecta\n");
return 1;
}
for(int i=0;i<n;i++)
{
if(fscanf(f,"%lf %lf",&puncte[i].x,&puncte[i].y)!=2)
{
printf("citire incorecta\n");
return 1;
}
}
qsort(puncte,n,sizeof(Point),comparare);
int top=0;
for(int i=0;i<n;i++)
{
while(top>=2 && cross(stiva[top-2],stiva[top-1],puncte[i])<=EPS)
{
top--;
}
stiva[top++]=puncte[i];
}
int limita_inf=top;
for(int i=n-2;i>=0;i--)
{
while(top>limita_inf && cross(stiva[top-2],stiva[top-1],puncte[i])<=EPS)
top--;
stiva[top++]=puncte[i];
}
top--;
fprintf(g,"%d\n",top);
for(int i=0;i<top;i++)
{
fprintf(g,"%.12lf %.12lf\n",stiva[i].x,stiva[i].y);
}
printf("gata\n");
fclose(f);
fclose(g);
return 0;
}