Pagini recente » Cod sursa (job #2836563) | Cod sursa (job #1918130) | Cod sursa (job #342023) | Cod sursa (job #1338992) | Cod sursa (job #281233)
Cod sursa(job #281233)
#include<stdio.h>
#define xx 120001
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
int n,pj,st[xx];
double x[xx],y[xx];
int det(int i,int j,int k)//adevarata cand are loc o intoarcere spre dreapta
{
double q;
q=((x[i]*y[j]+x[j]*y[k]+y[i]*x[k])-(x[k]*y[j]+x[j]*y[i]+x[i]*y[k]));
return (q<=0 ? 1 : 0); }
int poz(int li,int ls)
{
int aux,i=0,j=-1;
double auxx;
while(li<ls)
{
if(((x[li]-x[0])*(y[ls]-y[0]))<((x[ls]-x[0])*(y[li]-y[0])))
{
auxx=x[li]; x[li]=x[ls]; x[ls]=auxx;
auxx=y[li]; y[li]=y[ls]; y[ls]=auxx;
aux=-i; i=-j; j=aux;
}
li+=i;
ls+=j;
}
return li;
}
void qsort(int li,int ls)
{
int k;
if(li<ls)
{
k=poz(li,ls);
qsort(li,k-1);
qsort(k+1,ls);
}
}
int main()
{
int i,nr=0;
fscanf(fin,"%d",&n);
fscanf(fin,"%lf %lf",&x[1],&y[1]);
pj=1;
for(i=2;i<=n;i++)
{
fscanf(fin,"%lf %lf",&x[i],&y[i]);
if(x[pj]>x[i] || (x[pj]==x[i] && y[i]<y[pj]))
pj=i;
}
x[0]=x[pj];
y[0]=y[pj];
for(i=pj;i<n;i++)
{
x[i]=x[i+1];
y[i]=y[i+1];
}
x[n]=y[n]=0;
n--;
qsort(1,n);
st[++nr]=0;
for(i=1;i<=n;i++)
{
while(nr>=2 && det(st[nr-1],st[nr],i)) --nr;
st[++nr]=i;
}
st[++nr]=0;
while(nr>=3 && det(st[nr-2],st[nr-1],st[nr])) --nr;
fprintf(fout,"%d\n",nr-1);
for(i=1;i<nr;i++)
fprintf(fout,"%lf %lf\n",x[st[i]],y[st[i]]);
fclose(fout);
return 0;
}