Pagini recente » Cod sursa (job #335419) | Cod sursa (job #297431) | Cod sursa (job #242005) | Cod sursa (job #665693) | Cod sursa (job #404246)
Cod sursa(job #404246)
#include<fstream.h>
#include<iostream.h>
#define max 120002
double x[max],y[max];
long n,v[max],k,st[max],pas,i;
void coeficienti(double xa,double ya,double xb,double yb,double& aa,double& bb,double& cc)
{
aa=ya-yb;
bb=xb-xa;
cc=xa*yb-xb*ya;
}
long semn(double xa,double ya,double xb,double yb,double xc,double yc)
{
double aa,bb,cc;
coeficienti(xa,ya,xb,yb,aa,bb,cc);
if (aa*xc+bb*yc+cc<=0)
return -1; else
return 1;
}
void modifica()
{
if (pas==1)
{
i++;
if (i==n)
pas=-1;
} else
i--;
}
long divide(long p,long q)
{
long st=p,dr=q;
double x2=x[p],y2=y[p];
while (st<dr)
{
while ((st<dr && y[dr]>y2) || (st<dr && y[dr]==y2 && x[dr]>=x2))
dr--;
x[st]=x[dr];
y[st]=y[dr];
while ((st<dr && y[st]<y2) || (st<dr && y[st]==y2 && x[st]<=x2))
st++;
x[dr]=x[st];
y[dr]=y[st];
}
x[st]=x2;
y[st]=y2;
return st;
}
void qsort(long p,long q)
{
long m=divide(p,q);
if (m-1>p)
qsort(p,m-1);
if (m+1<q)
qsort(m+1,q);
}
void acoperire()
{
qsort(1,n);
pas=1;
st[1]=1; st[2]=2;
v[2]=1; k=2; i=2;
while (i>1)
{
while (v[i])
modifica();
if (i==0)
break;
while (k>1 && semn(x[st[k-1]],y[st[k-1]], x[st[k]],y[st[k]], x[i],y[i])==-1)
{
v[st[k]]=0;
k--;
}
k++;
st[k]=i;
v[i]=1;
}
}
int main()
{
long i;
ifstream fin("infasuratoare.in");
fin>>n;
for (i=1; i<=n; i++)
fin>>x[i]>>y[i];
fin.close();
acoperire();
ofstream fout("infasuratoare.out");
fout<<k-1<<'\n';
fout.setf(ios::fixed);
fout.precision(6);
for (i=1; i<=k-1; i++)
fout<<x[st[i]]<<" "<<y[st[i]]<<'\n';
fout.close();
return 0;
}