Pagini recente » Cod sursa (job #2980114) | Cod sursa (job #2611518) | Cod sursa (job #1885592) | Cod sursa (job #196643) | Cod sursa (job #3300614)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#define MAX_PUNCTE 120001
typedef struct
{
double x, y;
}punct;
punct puncte[MAX_PUNCTE];
int stiva[MAX_PUNCTE];
int varf=0;
int n;
int x_minim=INT_MAX,y_minim=INT_MAX,pozitie_minima;
double determinant(punct a,punct b,punct c)
{
return ((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
int compara(const void* p1, const void* p2)
{
punct a=*(punct*)p1;
punct b=*(punct*)p2;
double det=determinant(puncte[0],a,b);
return (det> 0) ? -1 : (det < 0) ? 1 : 0;
}
int main()
{
FILE *f,*out;
if((f=fopen("infasuratoare.in","r"))==NULL)
{
perror("Nu se poate deschide fisierul.");
exit(-1);
}
if((out=fopen("infasuratoare.out","w"))==NULL)
{
perror("Nu se poate deschide fisierul.");
exit(-1);
}
fscanf(f,"%d",&n);
for(int i=0;i<n;i++)
{
fscanf(f,"%lf %lf",&puncte[i].x,&puncte[i].y);
}
for(int i=0;i<n;i++)
{
if(puncte[i].x<x_minim)
{
x_minim=puncte[i].x;
}
}
for(int i=0;i<n;i++)
{
if(puncte[i].x==x_minim&&puncte[i].y<y_minim)
{
y_minim=puncte[i].y;
pozitie_minima=i;
}
}
punct temp=puncte[0];
puncte[0]=puncte[pozitie_minima];
puncte[pozitie_minima]=temp;
qsort(puncte+1,n-1,sizeof(punct),compara);
puncte[n]=puncte[0];
stiva[0]=0;
stiva[1]=1;
varf=1;
for(int i=2;i<=n;i++)
{
while(varf>0&&determinant(puncte[stiva[varf-1]],puncte[stiva[varf]],puncte[i])<0)
varf--;
stiva[++varf]=i;
}
fprintf(f,"%d\n",varf);
for(int i=1;i<=varf;i++)
fprintf(out,"%.6lf %.6lf\n",puncte[stiva[i]].x,puncte[stiva[i]].y);
fclose(f);
fclose(out);
return 0;
}