Pagini recente » Cod sursa (job #1566737) | Cod sursa (job #1873906) | Cod sursa (job #159063) | Cod sursa (job #590973) | Cod sursa (job #301306)
Cod sursa(job #301306)
#include<stdio.h>
FILE *f,*g;
const int Nmax=121000;
int lh,st[Nmax],st2[Nmax],vf,vf2;
long n,nr;
struct punct
{
double x,y;
}h[Nmax];
void urca(int k)
{
while(h[k].x<h[k/2].x)
{
punct z=h[k];
h[k]=h[k/2];
h[k/2]=z;
k=k/2;
}
}
void coboara(int k)
{
int fiu;
while(k<n)
{
fiu=k;
if(h[fiu].x>h[k*2].x && k*2<=lh)
fiu=2*k;
if(h[fiu].x>h[k*2+1].x && k*2+1<=lh)
fiu=2*k+1;
if(fiu!=k)
{
punct z=h[fiu];
h[fiu]=h[k];
h[k]=z;
k=fiu;
}
else
break;
}
}
void citire()
{
f=fopen("infasura.in","r");
g=fopen("infasura.out","w");
double a,b;
int i;
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(f,"%lf%lf",&a,&b);
h[++lh].x=a;
h[lh].y=b;
urca(lh);
}
for(i=1;i<=n;i++)
{
punct z=h[1];
h[1]=h[lh];
h[lh]=z;
lh--;
coboara(1);
}
}
void afisare()
{
for(int i=1;i<=vf;i++)
fprintf(g,"%.6lf %.6lf\n",h[st[i]].x,h[st[i]].y);
}
void traseu_jos()
{
int k=3;
st[1]=1;
st[2]=2;
vf=2;
while(k<=n)
{
while(h[k].y<h[st[vf]].y && h[st[vf-1]].y<h[st[vf]].y)
vf--;
st[++vf]=k++;
}
nr=vf;
//afisare();
}
void traseu_sus()
{
int k=3;
st2[1]=1;
st2[2]=2;
vf2=2;
while(k<=n)
{
while(h[k].y>h[st2[vf2]].y && h[st2[vf2-1]].y>h[st2[vf2]].y)
vf2--;
st2[++vf2]=k++;
}
}
int main()
{
citire();
traseu_jos();
traseu_sus();
fprintf(g,"%d\n",vf+vf2-2);
afisare();
for(int i=vf-1;i>0;i--)
fprintf(g,"%.6lf %.6lf\n",h[st2[i]].x,h[st2[i]].y);
fclose(f);
fclose(g);
return 0;
}