Pagini recente » Cod sursa (job #3136742) | Cod sursa (job #925200) | Cod sursa (job #932377) | Cod sursa (job #3181312) | Cod sursa (job #257693)
Cod sursa(job #257693)
#include<stdio.h>
#define xx 120001
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
double x[xx],y[xx];
int ind[xx],st[xx],n,pi;
inline int semn(int i,int j,int k)// adevarata cand are loc o intoarcere spre dreapta
{
return (((x[i]*y[j]+x[j]*y[k]+y[i]*x[k])-(x[k]*y[j]+x[j]*y[i]+x[i]*y[k]))>0 ? 1 : 0);
}
void quick(int,int);
int poz(int,int);
int main()
{
int i;
fscanf(fin,"%d",&n);
fscanf(fin,"%lf %lf",&x[1],&y[1]);
pi=1;
for(i=2;i<=n;i++)
{
fscanf(fin,"%lf %lf",&x[i],&y[i]);
if(x[i]<x[pi] || (x[i]==x[pi] && y[i]<y[pi]))
pi=i;
}
for(i=1;i<=n;i++)
if(i!=pi)
ind[++ind[0]]=i;
quick(1,ind[0]);
st[++st[0]]=pi;
for(i=1;i<=ind[0];i++)
{
while(st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i])) --st[0];
st[++st[0]]=ind[i];
}
fprintf(fout,"%lf\n",st[0]);
for(i=st[0];i>0;i--)
fprintf(fout,"%lf %lf\n",x[st[i]],y[st[i]]);
fclose(fout);
return 0;
}
void quick(int li,int ls)
{
if(li<ls)
{
int k;
k=poz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
int poz(int li,int ls)
{
int i=0,j=-1,aux;
while(li<ls)
{
if( (x[ind[li]]-x[pi])*(y[ind[ls]]-y[pi])>(x[ind[ls]]-x[pi])*(y[ind[li]]-y[pi]) )
{
aux=ind[li];
ind[li]=ind[ls];
ind[ls]=aux;
aux=-i;
i=-j;
j=aux;
}
li+=i;
ls+=j;
}
return li;
}