Pagini recente » Cod sursa (job #2030668) | smenuri | Cod sursa (job #2152487) | Cod sursa (job #3239596) | Cod sursa (job #281229)
Cod sursa(job #281229)
#include<fstream.h>
#define xx 120001
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
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;
fin>>n;
fin>>x[1]>>y[1];
pj=1;
for(i=2;i<=n;i++)
{
fin>>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;
}
fout<<nr<<'\n';
for(i=1;i<=nr;i++)
fout<<x[st[i]]<<' '<<y[st[i]]<<'\n';
fout.close();
return 0;
}